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

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

풀이

1. bfs로 상향식 풀이
2. bfs로 하향식 풀이

(상향식으로 풀었다가 시간초과가 나서 하향식으로 풀었는데, 알고보니 상향식 코드를 잘못 작성했다.... 황당..)

하향식 풀이의 경우 곱하기 대신 나누기를 사용하기 때문에 갑자기 int -> float 로 자료형 변화가 생겨서 애를 먹었다(라고 하기엔 잘 고쳤음).

# (bfs 중)
for num in [pos - n, pos / 2, pos / 3]:
	if num >= x and (num * 10 % 10) == 0 and not graph[int(num)]:
		queue.append(num)
		graph[int(num)] = graph[pos] + 1

위 코드에서 num 값이 float 가 될 수 있는 데, 그렇게 되면 배열의 인덱스 값으로 사용할 수 없음

• 해결 1 > 자연수의 경우에만 queue에 넣어줌

  • (num x 10 % 10 == 0) 인 경우 자연수 o
    ex) num=2.5인 경우, 2.5 x 10 % 10 = 5 이기 때문에 자연수 x
    ex) num=2인 경우, 2 x 10 % 10 = 0 이기 때문에 자연수o

• 해결 2 > num을 배열의 인덱스 값으로 사용할 때 int로 캐스팅

근데 이래저래 번거로우니 상향식으로 풀도록하자....

코드

상향식

from collections import deque

def solution(x, y, n):
    graph = [0] * (y + 1)
     
    def bfs():
        queue = deque([x])
        while queue:
            pos = queue.popleft()
            if pos == y:
                return graph[pos]
            for num in [pos + n, pos * 2, pos * 3]:
                if num <= y and not graph[num]:
                    queue.append(num)
                    graph[num] = graph[pos] + 1
        return -1
    
    answer = bfs()
    return answer

하향식

from collections import deque

def solution(x, y, n):
    graph = [0] * (y + 1)
     
    def bfs():
        queue = deque([y])
        while queue:
            pos = int(queue.popleft())
            if pos == x:
                return graph[pos]
            for num in [pos - n, pos / 2, pos / 3]:
                if num >= x and (num * 10 % 10) == 0 and not graph[int(num)]:
                    queue.append(num)
                    graph[int(num)] = graph[pos] + 1
        return -1
    
    answer = bfs()
    return answer