[코딩테스트] 프로그래머스 숫자 변환하기 파이썬(Python)

https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

 

from collections import defaultdict, deque
def solution(x, y, n):
    if x == y:
        return 0
    d = defaultdict(lambda :0)
    q = deque([x])
    while q:
        x= q.popleft()
        for next_x in [x+n, x*2, x*3]:
            if next_x > y:
                continue
            if d[next_x] > d[x]+1 or d[next_x] == 0:
                d[next_x] = d[x] + 1
                q.append(next_x)

    if d[y] == 0:
        return -1
    else:
        return d[y]

문제를 해결하는데 defaultdict와 deque 라이브러리를 사용하고 bfs알고리즘을 작성하였습니다.

• defaultdict : lambda : 0을 입력받음으로 모든키에 대해서 값이 없는 경우에 0으로 초기화해줍니다.

defaultdict 라이브러리로 노드의 깊이를 저장하는데 사용합니다.

 

x = 10, y = 40, n = 5 인 예제를 확인해보겠습니다.

그림에서 볼 수 있듯이 graph의 모습은 다음과 같습니다.

• 왼쪽 : x+n
• 중앙 : x*2
• 오른쪽 : x*3

graph에서 나올 수 있는 노드들을 구한뒤에 노드가 위치해있는 graph의 깊이를 확인합니다.

 

깊이가 2일때 40값을 구할 수 있습니다.

 

코드를 확인해보면

초기 x를 q에 저장한뒤에 bfs알고리즘을 수행합니다.

 

next_x는 현재 노드를 기준으로 다음노드(x+n, x*2, x*3)을 나타냅니다.

 

next_x가 y보다 커진다면 계산할 필요가 없기 때문에 continue를 사용하여 건너뜁니다.

 

다음 노드의 깊이가 현재 노드의 깊이 + 1보다 크거나 초기값 0으로 되어있는 경우에는
다음 노드의 깊이는 현재 노드의 깊이 + 1이 되고 q에 다음노드를 저장해줍니다.

 

bfs알고리즘이 종료된다면 문제의 target인 d[y]를 확인합니다

이때  bfs를 수행했음에도 d[y]가 0이라면 x를 y로 변환할 수 없다는 의미이기 때문에 -1을 반환합니다.

 

d[y]가 0이 아니라면 저장되어있는 d[y]를 반환합니다.