숫자 변환하기

왜 queue를 사용했는지?

최소 연산 횟수이기 때문에, 최단거리로도 생각해서 BFS 또는 DP로 풀이할 수 있을 것이라 생각했다.

왜 틀렸는지?

시간초과도 발생했고, 풀이실패도 있었다.
큐에 삽입된 요소의 값을 인덱스로만 접근하기 때문에 DP보다 접근 횟수는 적을 수 있으나, 조건문 판단 횟수가 많고, 동적 자료구조인 queue의 삽입, 삭제가 빈번해서 시간소모가 많이 발생했다. 또한 로직적으로 이미 접근한 값에 다른 연산횟수로 또 방문하는 경우가 생겨 연산 실패가 생겼다고 생각한다.

왜 DP를 사용했는지?

DP의 경우 x부터 y까지 모든 인덱스를 접근하지만, 조건문이 적고, 각 접근당 최소 연산 횟수를 지킬 수 있다. 그래서 수행속도와 정확도를 모두 챙겼다.

import java.util.*;

class State {
    int value;
    int count;

    State(int value, int count) {
        this.value = value;
        this.count = count;
    }
}

class Solution {
    public int solution(int x, int y, int n) {
        int answer = 0;
        
        //최소 연산?-> BFS or DP
        
        //DP로
        /*
        DP 배열 만들고
        x부터 시작해서 +n, *2, *3 한 값을 인덱스로 해당 원소에 횟수 +1
        y 인덱스를 넘어가면 continue;
        언제 종료? -> 큐를 사용해서 방문한 곳에서만 다시 시작하고, 큐가 비었으면 종료
        */
        
        int [] DP = new int[y + 1];
        int i;
        int next;
        
        Arrays.fill(DP, Integer.MAX_VALUE);
        DP[x] = 0;
        for(i = x; i <= y; i++){
            if(DP[i] == Integer.MAX_VALUE){
                continue;
            }
            
            //1. +n
            next = i + n;
            if(next > y){
                ;
            }
            else{
                DP[next] = Math.min(DP[next], DP[i] + 1);
            }
            
            //2. *2
            next = i * 2;
            if(next > y){
                ;
            }
            else{
                DP[next] = Math.min(DP[next], DP[i] + 1);
            }
           
            //3. *3
            next = i * 3;
            if(next > y){
                ;
            }
            else{
                DP[next] = Math.min(DP[next], DP[i] + 1);
            }
        }
        
        for(i = x; i <= y; i++){
            System.out.print(DP[i] + " ");
        }
        if(DP[y] == Integer.MAX_VALUE){
            answer = -1;
        }
        else{
            answer = DP[y];
        }
        
        /*
        // 실패 + 시간초과
        int current, current_count, next;
        Queue <State> q = new LinkedList<>();
        q.offer(new State(x, 0));
        answer = -1;
        
        
        while(!q.isEmpty()){
            current = q.peek().value;
            current_count = q.peek().count;
            q.poll();
            
            //1. +n
            next = current + n;
            if(next == y){
                answer = current_count + 1;
                break;
            }
            else if(next < y){
                q.offer(new State(next, current_count + 1));
            }
            else{ // next > y
                ;
            }
            
            //2. *2
            next = current * 2;
            if(next == y){
                answer = current_count + 1;
                break;
            }
            else if(next < y){
                q.offer(new State(next, current_count + 1));
            }
            else{ // next > y
                ;
            }
            
            
            //3. *3
            next = current * 3;
            if(next == y){
                answer = current_count + 1;
                break;
            }
            else if(next < y){
                q.offer(new State(next, current_count + 1));
            }
            else{ // next > y
                ;
            }
        }
        */
        
        return answer;
    }
}