[프로그래머스] 숫자 변환하기 (Java)

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

프로그래머스

import java.util.*;

class Solution {
    int[] cost = new int[3000001];
    static class Item implements Comparable<Item>{
        int number;
        int dist;
        Item(int number, int dist){
            this.number = number;
            this.dist = dist;
        }
        @Override
        public int compareTo(Item other){
            if (this.number == other.number){
                return this.dist - other.dist;
            }
            return this.number - other.number;
        }
    }
    public int solution(int x, int y, int n) {
        int answer = 0;
        PriorityQueue<Item> pq = new PriorityQueue<>();
        Arrays.fill(cost, Integer.MAX_VALUE);
        pq.add(new Item(x, 0));
        cost[x] = 0;
        while (!pq.isEmpty()){
            Item item = pq.poll();
            if (item.number > y){
                answer = -1;
                break;
            }
            if (item.number == y){
                answer = item.dist;
                break;
            }
            int[] values = {item.number + n, item.number * 2, item.number * 3};
            for (int i=0; i<3; i++){
                if (cost[values[i]] > item.dist+1){
                    pq.add(new Item(values[i], item.dist+1));
                    cost[values[i]] = item.dist + 1;
                }
            }
        }
        return answer;
    }
}

다익스트라 느낌났던 문제

 

pq + dp 배열(cost) 를 써서 현재 숫자까지 도착 거리가 제일 짧은 애를 탐색하도록 한다

가장 짧은 애가 튀어나올 수 있도록, (숫자, 거리)를 나타내는 Item을 정렬할 때 숫자 작은 순, 거리 작은 순으로 정렬하도록 했다