[프로그래머스 / 파이썬] 숫자 변환하기

프로그래머스 2 레벨 문제이다.

문제 주소: https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

문제 해석

딱히 해석할 내용이 없다.. 

x, y, n이 주어지며 다음과 같은 3가지 규칙이 주어진다.

1. n 더하기
2. 2 곱하기
3. 3 곱하기

위 3가지 규칙을 이용해서 x를 y로 변환하는 최단 연산 횟수를 구하는 문제이다.

문제 풀이

3가지 연산 규칙은 cal 함수를 만들어 따로 구현해주었다.

bfs를 통해 같은 연산 횟수 내에서 순차적으로 답을 찾아나가면 된다.

재귀로 접근하지 않고 bfs 연산을 하는 이유는 재귀로 접근할 경우 n 더하기 연산을 우선적으로 반복한다.
즉, n이 2라면 2, 4, 6, 8, ... 다음과 같은 순서대로 반복한다.
하지만 2 곱하기 연산을 통해 2, 4, 8, ... 로 더 빨리 도달할 수 있는 경우가 생긴다.
따라서 bfs 연산을 통해 중복된 연산은 계산하지 않도록 구현할 수 있다.

bfs를 통해 순차적으로 답을 구해나간다. 이때 방문처리를 통해 중복 방문한 숫자는 방문하지 않도록 구현하면 답을 구할 수 있다.

문제 코드

from collections import deque
mem = [-1] * 1_000_001

def cal(num, n, i):
    if i == 0: 
        return num + n
    elif i == 1: 
        return num * 2
    return num * 3

def bfs(num, y, n):
    q = deque()
    q.append(num)
    mem[num] = 0
    while q:
        for _ in range(len(q)):
            cur = q.popleft()
            for i in range(3):
                nxt = cal(cur, n, i)
                if not (1 <= nxt < 1_000_001): 
                    continue
                if mem[nxt] == -1:
                    mem[nxt] = mem[cur] + 1
                    q.append(nxt)
                elif mem[nxt] > mem[cur] + 1:
                    mem[nxt] = mem[cur] + 1
                    q.append(nxt)
    return

def solution(x, y, n):
    mem[x] = 0
    bfs(x, y, n)
    answer = mem[y]
    return answer

예제 결과