[Programmers] 숫자 변환하기(Lv.2) - Java

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

프로그래머스

[문제설명]

자연수 x를 y로 변환하려 한다.

 

방법은 3가지가 있는데

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

x, y, n이 주어졌을 때 최소 연산의 횟수를 구하는 문제이다.

 

나는 BFS를 생각했는데

 

1 <= x, y <= 1,000,000 이란 제약조건에서 충분히 탐색이 가능하다고 생각했고

 

사실 탐욕법같은걸로도 풀 수 있을 것 같지만 식세우는걸 잘 못해서..

 

자세한 건 주석으로!

 

[소스코드]

import java.util.*;

class Solution {
	//x에 적절한 연산을 취한 횟수와 그 결과를 저장할 Class
    static class Node{
        int num;
        int count;
        Node(int num, int count){
            this.num = num;
            this.count = count;
        }
    }
    static Queue<Node> q;
    static boolean[] visited;
    static int limit = 1000000;
    public int solution(int x, int y, int n) {
        int answer = 0;
        if(x == y)
            return 0;
        q = new LinkedList<>();
        
        //제일 큰 수가 나오는게 3을 곱하는 것이고 각 인덱스를 숫자 그대로 보기위해서 +1
        visited = new boolean[3*limit+1];
        q.offer(new Node(x, 0));
        
        while(!q.isEmpty()){
            Node cur = q.poll();
            int curNum = cur.num;
            int curCount = cur.count;
            if(curNum == y){
                answer = curCount;
                break;
            }
            //각 연산을 취했을 때 나온적이 없는 수인지(!visited)
            //그리고 그 수가 제한조건을 넘어가지 않는지
            if(!visited[curNum+n] && curNum+n <= limit){
                visited[curNum+n] = true;
                q.offer(new Node(curNum+n, curCount+1));
            }
            if(!visited[curNum*2] && curNum*2 <= limit){
                visited[curNum*2] = true;
                q.offer(new Node(curNum*2, curCount+1));
            }
            if(!visited[curNum*3] && curNum*3 <= limit){
                visited[curNum*3] = true;
                q.offer(new Node(curNum*3, curCount+1));
            }
        }
        return answer == 0 ? -1 : answer;
    }
}