프로그래머스 Lv2 숫자 변환하기 (python)

숫자 변환하기

풀이

처음에는 재귀로 풀려고 했다가 너무 많은 재귀로 실패해서, 이후엔 어떻게 풀어야 하는지 감도 안 잡혔다.
찾아보니 BFS나 DP로 풀어야 한다고 했다.

너무 오랜만에 만지는 BFS라 감을 잃었지만 다시 시도해봤다.
우선 다음처럼 풀었다.
1. visited를 생성
2. queue를 생성하고 Q에 초깃값으로 x를 입력
3. visited [x]를 0에서 1로 입력
3-1. 찾고 나서 1빼줄건데, 1로 해준 이유는 0을 False처럼 다루기 위해서임
4. while문을 진행하기. Q의 처음 값을 확인하고, y가 아니면 할 수 있는 3가지를 이용하기. 3가지가 제한 없는 내용이라면, visited [다음 수]에 visited [이전 수]+1 입력
5. 3가지 방법을 통해서 나온 중 Q에서 뽑아낸 값이 y랑 동일하다면 visited [해당 수] -1을 return
6. 만약 없어서 while문을 벗어나면 return -1

추가로 처음에 front rear가 아닌 pop(0)의 방식을 사용하니 시간 초과가 났다. 여기서도 append도 안 쓰고 싶었지만, 숫자가 언제까지 나오게 될지 알 수 없었기에 append를 사용했다.
확실히 pop() 대신 front rear 방식으로 바꾸니 시간속도가 엄청 빨라졌다.

# BFS 방법을 이용
def solution(x, y, n):
    # 1~ 1000000까지니까 visited는 인덱스가 1000000이 될 수 있게 구성
    visited = [0] * 1000001
    # Q의 초깃값에 x 입력
    Q = [x]
    front = 0
    rear = 0
    # x값에 방문했음을 입력
    visited[x] = 1
    # Q에 값이 있고, n이 나올 때 까지 진행
    while front <= rear:
        node = Q[front]
        # x 값이 y랑 같으면 visited[x]에서 -1 빼면 최소연산 횟수가 됨
        if node == y:
            return visited[node] - 1
        # 기존 x에 할 수 있는 행동 3가지를 반복문을 돌려서 Q에 입력시키기.
        # visited[]에는 현재 x까지 온 횟수에 + 1 하기
        for next in [node + n, node * 2, node * 3]:
            if 1 <= next <= 1000000 and not visited[next] and next <= y:
                Q.append(next)
                rear += 1
                visited[next] = visited[node] + 1
        front += 1
    # 이 모든 과정을 하면서도 없으면 안되는 거니까 -1
    return -1

다른 사람 풀이

이 방법도 BFS지만 queue와 visited대신 set()을 이용하여 풀었다.
1. s라는 set()을 생성하고 x를 s에 추가
2. s에 값이 있을 동안 반복하며, y값이 s에 존재하면 answer 즉, 반복 횟수를 입력
3. nxt라는 새로운 set()을 생성하고, 제한사항에 맞게 3가지 +n 2, 3을 nxt에 입력 후, s를 nxt로 바꿔주고, answer += 1하기
4. 2와 3을 반복. 이때 while문을 벗어나면 x에서 y로 갈 수 없음이 되므로 return -1

def solution(x, y, n):
    answer = 0
    s = set()
    s.add(x)

    while s:
        if y in s:
            return answer

        nxt = set()
        for i in s:
            if i+n <= y:
                nxt.add(i+n)
            if i*2 <= y:
                nxt.add(i*2)
            if i*3 <= y:
                nxt.add(i*3)
        s = nxt
        answer+=1

    return -1