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

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

숫자 변환하기

문제

📌 문제 설명

자연수 x를 시작점으로 하여 y를 만들고자 합니다. 사용할 수 있는 연산은 다음 세 가지입니다:

• x에 n을 더함 → x + n
• x에 2를 곱함 → x * 2
• x에 3을 곱함 → x * 3

이 연산들을 반복하여 x를 y로 변환하고자 할 때, 필요한 최소 연산 횟수를 구하는 문제입니다.
만약 어떤 방법으로도 y를 만들 수 없다면, -1을 반환해야 합니다.

테스트케이스

x	y	n	반환값
10	40	5	2
10	40	30	1
2	5	4	-1

---

작동원리

🔄 연산 방식

• x에서 시작하여, 가능한 연산 +n, *2, *3을 이용해 다음 숫자들을 만들어갑니다.
• 이 숫자들이 y보다 작거나 같을 때만 유효하며, 이를 계속해서 반복합니다.

🔁 BFS (너비 우선 탐색) 사용

• BFS는 현재 상태에서 가능한 모든 다음 상태를 시도하며, 가장 먼저 목표에 도달하는 경로를 찾는 데 적합합니다.
• 따라서 연산 횟수를 최소로 하여 y를 만드는 방법을 찾기 위해 BFS를 선택합니다.

🧱 중복 방지 처리 (visited)

• 이미 확인한 숫자는 다시 확인하지 않기 위해 visited라는 집합(set)을 사용합니다.
• 같은 숫자가 여러 경로로 다시 나오는 것을 막아 불필요한 연산을 줄이고, 시간 초과를 방지합니다.

---

아이디어

1. deque를 사용하여 큐를 만들고 시작 숫자와 연산 횟수 0을 함께 넣습니다.
2. 큐에서 숫자를 꺼내며 다음 세 가지 연산을 각각 적용합니다:
   • x_now + n
   • x_now * 2
   • x_now * 3
3. 이 세 결과 중 y보다 작거나 같은 수들만 다음 탐색 대상으로 삼습니다.
4. 이미 방문한 숫자(visited)는 다시 큐에 넣지 않습니다.
5. 현재 숫자가 y가 되면 해당 연산 횟수를 반환합니다.
6. 큐가 모두 비워질 때까지 y에 도달하지 못하면, -1을 반환합니다.

---

전체코드

from collections import deque

def solution(x, y, n):
    answer = 0
    q = deque()
    visited = set()
    q.append([x, 0])

    while q:
        x_now, level = q.popleft()

        if x_now == y:
            return level
            break

        if x_now * 2 <= y and not x_now * 2 in visited:
            q.append([x_now * 2, level + 1])
            visited.add(x_now * 2)
        if x_now * 3 <= y and not x_now * 3 in visited:
            q.append([x_now * 3, level + 1])
            visited.add(x_now * 3)
        if x_now + n <= y and not x_now + n in visited:
            q.append([x_now + n, level + 1])
            visited.add(x_now + n)
    return -1
    

---

결론

• BFS 탐색 방식을 사용하여 가능한 모든 경로를 효율적으로 탐색하였습니다.
• visited 집합을 활용하여 중복 계산을 차단하고 시간 초과 문제를 해결하였습니다.
• 이 코드는 문제에서 요구한 제한사항(최대 1,000,000까지의 숫자)을 만족시키며, 다양한 케이스에서 정확하게 작동합니다.
• 핵심은 최소 연산 횟수를 찾기 위한 탐색 방식 선택(BFS)과, 방문 처리(visited)를 통한 효율성 확보에 있습니다.