숫자 변환하기

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

def solution(x, y, n):
    que = [(x, 0)]
    while que:
        x_, answer = que.pop(0)
        if x_ > y:
            continue
        if x_ == y:
            return answer
        que.append((x_ * 2, answer + 1))
        que.append((x_ * 3, answer + 1))
        que.append((x_ + n, answer + 1))
    return -1

너비우선탐색(BFS) 으로...

넓이 아님~

테스트 1 〉	통과 (0.01ms, 10.3MB)
테스트 2 〉	통과 (0.00ms, 10MB)
테스트 3 〉	통과 (0.00ms, 10MB)
테스트 4 〉	통과 (0.00ms, 10.3MB)
테스트 5 〉	실패 (시간 초과)
테스트 6 〉	통과 (0.00ms, 10.2MB)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	통과 (0.00ms, 10.1MB)
테스트 9 〉	실패 (시간 초과)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	실패 (시간 초과)
테스트 12 〉	통과 (0.00ms, 10MB)
테스트 13 〉	통과 (0.00ms, 10.1MB)
테스트 14 〉	통과 (219.06ms, 16MB)
테스트 15 〉	통과 (0.22ms, 10.2MB)
테스트 16 〉	통과 (4.61ms, 10.6MB)

deque를 사용하면 통과할까?

from collections import deque


def solution(x, y, n):
    que = deque([(x, 0)])
    while que:
        x_, answer = que.popleft()
        if x_ > y:
            continue
        if x_ == y:
            return answer
        que.append((x_ * 2, answer + 1))
        que.append((x_ * 3, answer + 1))
        que.append((x_ + n, answer + 1))
    return -1

테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.00ms, 10.2MB)
테스트 3 〉	통과 (0.01ms, 10MB)
테스트 4 〉	통과 (0.01ms, 10.1MB)
테스트 5 〉	실패 (시간 초과)
테스트 6 〉	통과 (0.00ms, 10.2MB)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	통과 (0.00ms, 10MB)
테스트 9 〉	실패 (시간 초과)
테스트 10 〉	실패 (시간 초과)
테스트 11 〉	실패 (시간 초과)
테스트 12 〉	통과 (0.01ms, 10.4MB)
테스트 13 〉	통과 (0.00ms, 10MB)
테스트 14 〉	통과 (19.67ms, 15.8MB)
테스트 15 〉	통과 (0.19ms, 10.1MB)
테스트 16 〉	통과 (2.68ms, 10.7MB)

반복을 줄여주면..

from collections import deque


def solution(x, y, n):
    que = deque([(x, 0)])
    visited = set()
    while que:
        x_, answer = que.popleft()
        if x_ > y or x_ in visited:
            continue
        if x_ == y:
            return answer
        visited.add(x_)
        que.append((x_ * 2, answer + 1))
        que.append((x_ * 3, answer + 1))
        que.append((x_ + n, answer + 1))
    return -1

 

테스트 1 〉	통과 (0.01ms, 10.3MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.01ms, 10.3MB)
테스트 4 〉	통과 (0.01ms, 10.2MB)
테스트 5 〉	통과 (70.06ms, 24.7MB)
테스트 6 〉	통과 (0.00ms, 10.2MB)
테스트 7 〉	통과 (69.35ms, 24.9MB)
테스트 8 〉	통과 (0.01ms, 10.3MB)
테스트 9 〉	통과 (387.23ms, 94.3MB)
테스트 10 〉	통과 (304.75ms, 85.3MB)
테스트 11 〉	통과 (108.02ms, 37.8MB)
테스트 12 〉	통과 (0.01ms, 10.2MB)
테스트 13 〉	통과 (0.01ms, 10.2MB)
테스트 14 〉	통과 (2.38ms, 10.6MB)
테스트 15 〉	통과 (0.10ms, 10.4MB)
테스트 16 〉	통과 (0.66ms, 10.4MB)

 

DP로...

def solution(x, y, n):
    dp = {x: 0}
    for i in range(x, y + 1):
        if i not in dp:
            continue
        if i + n <= y:
            dp.setdefault(i + n, float('inf'))
            dp[i + n] = min(dp[i + n], dp[i] + 1)
        if i * 2 <= y:
            dp.setdefault(i * 2, float('inf'))
            dp[i * 2] = min(dp[i * 2], dp[i] + 1)
        if i * 3 <= y:
            dp.setdefault(i * 3, float('inf'))
            dp[i * 3] = min(dp[i * 3], dp[i] + 1)
    return dp[y] if y in dp else -1

테스트 1 〉	통과 (18.18ms, 10.4MB)
테스트 2 〉	통과 (1.49ms, 10.2MB)
테스트 3 〉	통과 (4.09ms, 10.3MB)
테스트 4 〉	통과 (0.17ms, 10.2MB)
테스트 5 〉	통과 (214.78ms, 20.1MB)
테스트 6 〉	통과 (0.00ms, 10.3MB)
테스트 7 〉	통과 (124.41ms, 20.1MB)
테스트 8 〉	통과 (61.29ms, 10.1MB)
테스트 9 〉	통과 (1501.29ms, 91.7MB)
테스트 10 〉	통과 (1260.02ms, 91.7MB)
테스트 11 〉	통과 (732.16ms, 50.8MB)
테스트 12 〉	통과 (12.51ms, 10.1MB)
테스트 13 〉	통과 (3.99ms, 10.3MB)
테스트 14 〉	통과 (319.70ms, 32MB)
테스트 15 〉	통과 (59.76ms, 11.3MB)
테스트 16 〉	통과 (73.20ms, 12.6MB)