[프로그래머스 / Java] - 숫자 변환하기

문제 설명

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

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

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

 

제한사항

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

 

정답 설명

문제를 해결할 수 있는 간단하면서도 효율적인 방법은 그래프 탐색이다. 즉, 특정 숫자 x에 대해 x+n, x*2, x*3 의 값을 확인 하고, 이 3개의 결과값을 다시 x로 생각하여 x+n, x*2, x*3 의 값을 확인하는 식으로 BFS를 사용하여 문제를 해결할 수 있다. 그러나, 이 BFS의 단점은 이미 확인했던 경우를 반복하여 확인하는 것에 있다. 때문에 이전에 사용한 결과값을 기억하는 DP를 함께 활용하는 방법으로 시간을 단축시킬 수 있다.

 

DP를 활용하는 방법은 간단하다. 한번 확인한 결과값에 대한 연산 횟수를 저장해 두고, 같은 연산 결과가 다시 발생한다면 연산을 더 진행하지 않는 방법이다. 이 때, 특정 결과값 $a$에 대한 연산 횟수 $f(a)$를 배열에 저장하는 것은 효율적이지 못하다. 우리가 저장하게 될 값은 전체 자연수의 값이 아닌, 특정 연산에 대한 결과 값이기 때문에 배열에서 한번도 방문하지 않는 공간이 존재할 가능성이 크기 때문이다. HashMap<Integer, Integer>를 이용해 key 값를 얻기 위한 연산 횟수를 value로 저장하자.

 

문제 해결 과정은 다음과 같다.

1. Queue에 x를 삽입하고, HashMap에 <x, 0>을 저장한다.
2. Queue가 빌 때 까지 Queue에서 숫자 k를 하나씩 꺼낸다.
   1. HashMap에 저장되어 있는 key k에 대한 연산 횟수 f(k)를 가져온다.
   2. 숫자 k에 대해 세가지 연산 ( k+n, k*2, k*3)을 수행한다.
   3. 연산을 수행한 결과가 y와 같다면 f(k) + 1을 반환한다.
   4. 연산 수행 결과 r이 y 보다 작다면 Queue에 연산 결과를 삽입하고, HashMap에 <r, f(k) + 1>을 저장한다.
3. Queue가 텅 비면 -1을 반환한다.

 

소스 코드

import java.util.*;
class Solution {
    public int solution(int x, int y, int n) {
        HashMap<Integer, Integer> count = new HashMap<>();
        Queue<Integer> q = new LinkedList<>();
        int curNum;
        
        q.add(x);
        count.put(x, 0);
        
        if(x == y)
            return 0;
        
        while(!q.isEmpty() && (curNum = q.poll()) != y){
            int opCount = count.get(curNum);
            
            int result = curNum + n;
            if(result == y){
                return opCount + 1;
            }else if(result < y && !count.containsKey(result)){
                count.put(result, opCount + 1);
                q.add(result);
            }
            
            result = curNum * 2;
            if(result == y){
                return opCount + 1;
            }else if(result < y && !count.containsKey(result)){
                count.put(result, opCount + 1);
                q.add(result);
            }
            
            result = curNum * 3;
            if(result == y){
                return opCount + 1;
            }else if(result < y && !count.containsKey(result)){
                count.put(result, opCount + 1);
                q.add(result);
            }
        }
        
        return -1;
    }
}