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

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

접근

자연수 x를 y로 변환하려고 한다.
y로 변환하고자 할 때, 방법은 아래의 세가지로 가능하다.

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

효율로 따져보면 x에 곱하기 연산을 하는 것이 더하기 연산을 하는 것보다 좋을 것으로 예상할 수 있다.

그리고 x,y의 값이 최대 1백만이므로 O(N)이나 O(NlogN)정도 되는 알고리즘을 생각해볼 수 있다.

풀이 1 (시간초과)

처음에는 문제에서 요구한대로 x에서 y로의 변환을 시도했다.
방법은 간단하다.

	Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(x,0));
        while(!q.isEmpty()){
            Pair p = q.poll();
            int cur = p.cur, cnt = p.cnt;

            if (cur > y) continue;
            if(cur == y) return cnt;

            q.add(new Pair(cur*3,cnt+1));
            q.add(new Pair(cur*2,cnt+1));
            q.add(new Pair(cur+n,cnt+1));
        }

• 큐를 하나 선언하고, 초기 값인 x를 넣는다. (횟수를 구해야 하므로 cnt도 넣어줌)
• x3, x2, x+n을 큐에 넣는다.
• 만약 해당 값이 y에 도달하면 cnt 값을 리턴한다. 아니면 계속 반복

그런데 이 방법으로 풀었을 때 시간초과가 났다...
x와 n이 작은 값이고 y가 큰 경우에, x*3, x*2, x+n 을 하면 중복되는 연산이 굉장히 많아지고 비효율적인 알고리즘이 된다.

풀이 2

이러한 문제를 해결한 방법은, 접근을 반대로 하는 것이었다.
x->y 로의 변환이 아닌, y->x로의 변환을 생각하였다.

	Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(y,0));
        
        while(!q.isEmpty()){
            Pair p = q.poll();
            int cur = p.cur, cnt = p.cnt;
            
            if (cur < x) continue;
            if(cur == x) return cnt;
            
            if(cur%3==0) q.add(new Pair(cur/3,cnt+1));
            if(cur%2==0) q.add(new Pair(cur/2,cnt+1));
            q.add(new Pair(cur-n,cnt+1));
            
        }

이렇게 하였을 때, y/3 y/2 연산이 자연수가 되는 경우만 따지므로, 자연수가 아니게 되는 경우가 전부 소거된다.
그러므로 곱하기 연산을 했을 때보다 연산 수가 획기적으로 줄게 되는 것이다.

단순히 반대로 생각하는 것만으로도 문제를 해결할 수 있다는 것을 깨닫게 되는 문제였다.

정답코드

import java.util.*;

class Pair{
    int cur, cnt;
    Pair(int cur, int cnt){
        this.cur = cur;
        this.cnt = cnt;
    }
}

class Solution {

    public int solution(int x, int y, int n) {
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(y,0));
        
        while(!q.isEmpty()){
            Pair p = q.poll();
            int cur = p.cur, cnt = p.cnt;
            
            if (cur < x) continue;
            if(cur == x) return cnt;
            
            if(cur%3==0) q.add(new Pair(cur/3,cnt+1));
            if(cur%2==0) q.add(new Pair(cur/2,cnt+1));
            q.add(new Pair(cur-n,cnt+1));
            
        }
        
        return -1;
        
    }

}