[프로그래머스>Lv2] 숫자 변환하기

프로그래머스

 

1. 문제

자연수 x를 y로 변환하려고 합니다.

• x에 n을 더합니다.
• x에 2를 곱합니다.
• x에 3을 곱합니다.

 

[입력]

자연수 x, y, n

 

[출력]

x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return

🌹 x를 y로 만들 수 없다면 -1을 return

 

2. 풀이

문제를 보면 딱 너비우선탐색(BFS)을 사용하여 풀 수 있는 전형적인 문제입니다.

하나의 수에서 진행할 수 있는 경로는 3가지가 있습니다.

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

위 경로를 순차적으로 탐색하다, y와 만나면 연산 횟수를 반환하면 됩니다.

 

* 이 때, 연산의 결과가 y보다 커질 경우에는 더 이상 진행하지 않는다는 조건문이 중요합니다.

만약 이를 추가하지 않는다면 무한루프에 갇히게 될 것입니다. 🤗👍🏻

 

그리고 또한 동일한 숫자를 여러번 탐색하지 않도록 cache를 추가해주도록 하겠습니다.

 

3. 코드

kotlin

import java.util.PriorityQueue

class Solution {
    fun solution(x: Int, y: Int, n: Int): Int {
        // 숫자, 연산 횟수
        val queue = PriorityQueue<Pair<Int, Int>> { a, b -> a.first - b.first }
        queue.add(x to 0)
        val cache = IntArray(y + 1) { y + 1 }

        while (queue.isNotEmpty()) {
            val (number, time) = queue.poll()!!

            if (number == y) return time

            if (number + n <= y && cache[number + n] > time + 1 ) {
                cache[number + n] = time + 1
                queue.add(number + n to time + 1)
            }
            if (number * 2 <= y && cache[number * 2] > time + 1) {
                cache[number * 2] = time + 1
                queue.add(number * 2 to time + 1)
            }
            if (number * 3 <= y && cache[number * 3] > time + 1) {
                cache[number * 3] = time + 1
                queue.add(number * 3 to time + 1)
            }
        }
        return -1
    }
}

 

python

from heapq import heappush, heappop
def solution(x, y, n):
    answer = 0
    
    queue = []
    heappush(queue, (x, 0))
    cache = [y+1] * (y+1)
    
    while queue:
        num, time = heappop(queue)
        
        if num == y:
            return time
        
        if num + n <= y:
            if cache[num+n] > time+1:
                cache[num+n] = time+1
                heappush(queue, (num+n, time+1))
        if num * 2 <= y:
            if cache[num*2] > time+1:
                cache[num*2] = time+1
                heappush(queue, (num*2, time+1))
        if num * 3 <= y:
            if cache[num*3] > time+1:
                cache[num*3] = time+1
                heappush(queue, (num*3, time+1))
            
    return -1