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

문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/154538

Problem

BFS와 Memoization을 같이 활용한 문제입니다.

x,y,n이 주어지고, x -> y 로 매핑을 하는데, 방법은 세가지가 있습니다.

1. x + n
2. x * 2
3. x * 3

이중 가능한 최소 연산의 수를 반환하면 됩니다. 만약 가능하지 않다면 -1을 반환합니다.

Approach & Solution

처음에는 그냥 BFS로 접근했습니다. DP 냄새가 나기도 했지만, 쉬운건 쉽게 푸는게 맞다고 생각해서 BFS로 접근했는데, 결국 돌아가는 느낌이었네요ㅋㅋㅋ

from collections import deque

def solution(x, y, n):
    answer = []
    qq = deque()
    qq.append([x,0])
    
    while qq:
        num,trial = qq.popleft()
            
        if num == y:
            answer.append(trial)
        else:
            if (num + n) <= y:
                qq.append([num + n, trial + 1])
            if (num * 2) <= y:
                qq.append([num * 2, trial + 1])
            if (num * 3) <= y:
                qq.append([num * 3, trial + 1])
        
    if answer:
        return min(answer)
    else:
        return -1

첫 풀이는 제가 봐도 많은 케이스를 접근하는게 보입니다. 결국 시간초과가 나기도 했구요. 그래서 memoization을 해줘서 그 전에 봤던 케이스는 그냥 스킵하게 만들어 주었습니다.

from collections import deque
from collections import defaultdict

def solution(x, y, n):
    answer = []
    qq = deque()
    qq.append([x,0])
    visited = defaultdict(int)
    while qq:
        num,trial = qq.popleft()
        
        if num != y and visited[num] == 1:
            continue
        else:
            visited[num] = 1
            
        if num == y:
            answer.append(trial)
        else:
            if (num + n) <= y:
                qq.append([num + n, trial + 1])
            if (num * 2) <= y:
                qq.append([num * 2, trial + 1])
            if (num * 3) <= y:
                qq.append([num * 3, trial + 1])
        
    if answer:
        return min(answer)
    else:
        return -1

visited = defaultdict(int) 를 도입해서 체크한 케이스를 넘깁니다.

Conclusion

BFS에서 Memoization을 접목한 문제는 처음이어서 포스팅을 해봤습니다. 결국 크게보면 백트래킹일수도 있겠네요.