[프로그래머스] 숫자 변환하기

문제

[프로그래머스] 숫자 변환하기

실패 코드 - 시간 초과

from collections import deque

def bfs(x,y,n):
    queue = deque()
    queue.append((x, 0))
    
    while queue:
        nx, cnt = queue.popleft()
        
        if nx == y:
            return cnt
        
        for i in range(3):
            ax = 연산(nx, n, i)
            if ax <= y:
                queue.append((ax, cnt+1))
    return -1

def 연산(x, n, i):
    if i == 0:
        return x+n
    elif i == 1:
        return x*2
    else:
        return x*3
            
        
def solution(x, y, n):
    return bfs(x,y,n)

• 제출했을 때, 몇 가지 테스트 케이스에서 시간 초과가 발생했다.

정답 코드

from collections import deque

def bfs(x,y,n):
    queue = deque()
    dic = {}
    queue.append((x, 0))
    dic[x] = 0
    
    while queue:
        nx, cnt = queue.popleft()
        
        if nx == y:
            return cnt
        
        for i in range(3):
            ax = 연산(nx, n, i)
            if ax <= y and ax not in dic:
                queue.append((ax, cnt+1))
                dic[ax] = cnt+1
    return -1

def 연산(x, n, i):
    if i == 0:
        return x+n
    elif i == 1:
        return x*2
    else:
        return x*3
            
        
def solution(x, y, n):
    return bfs(x,y,n)

• 기존 코드에서 3가지 연산한 값을 모두 queue에 넣어서 시간 초과가 발생한 것이었다.
• 딕셔너리 코드를 추가했다.
• queue와 동시에 딕셔너리에도 값을 넣어줬다. 다만, 이미 딕셔너리에 있는 값은 더 적은 횟수로 계산된 적이 있다는 의미이므로 queue에 append해주지 않았다.