숫자 변환하기

https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

 

최소연산횟수이므로 너비우선탐색으로 해결했다.

 

cache를 두어서, 연산 횟수가 적은 값이 후에 또 등장했을 때 추가적인 연산을 막아주었다. 이 cache가 없으면 시간 초과 떴던듯..

 

import java.util.*;

class Solution {
        
    public int solution(int x, int y, int n) {
        return calc(x, n, y);
    }
    
    int calc(int x, int n, int y) {
        
        boolean[] cache = new boolean[y+1];
        
        Queue<Num> q = new LinkedList();
        q.add(new Num(x));
        
        while(!q.isEmpty()) {
            
            Num num = q.poll();
            
            if (num.num == y) return num.cnt;
            
            if (num.num > y) continue;
            
            if (cache[num.num]) continue;
            cache[num.num] = true;
            
            q.add(num.plus(n));
            q.add(num.twice());
            q.add(num.triple());
            
        }
        
        return -1;
        
    }
    
    static class Num {
        int num;
        int cnt;
        Num(int num) {
           this.num = num;
        }
        Num plus(int p) {
            Num n = new Num(this.num + p);
            n.cnt = this.cnt + 1;
            return n;
        }
        Num twice() {
            Num n = new Num(this.num * 2);
            n.cnt = this.cnt + 1;
            return n;
        }
        Num triple() {
            Num n = new Num(this.num * 3);
            n.cnt = this.cnt + 1;
            return n;
        }
    }
    
}