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

프로그래머스

접근 방식

숫자 x를 주어진 세 가지 방식을 활용하여 y로 변환할 수 있는 최소 횟수를 구하는 문제로, BFS로 접근하여 풀어냈다. 변환된 각각의 숫자를 하나의 Node로 보고, 한 번 변환될 때마다 Node에 숫자 number와 그 숫자가 되기까지의 변환 횟수를 count 변수에 저장하도록 했다. 문제 설명대로라면 x에서 시작하여 y까지 가야하는 게 맞지만, y에서 시작하는 것이 경우의 수 소거에 유리하여 반대 방향으로 시작했다.

로직 설명

- Node 클래스(이하 노드) 생성: 멤버변수 number, count

- BFS를 구현하기 위해 필요한 노드 큐 생성: queue

- 노드를 생성하여(number: y, count: 0) queue에 넣기

- queue에 노드가 존재하는 동안 반복:

  1) 노드 한 개 poll()

  2) (노드의 number가 x와 같을 경우), answer에 노드 count 값 저장 후 루프 종료

  3) (아닐 경우) 노드의 number를 3으로 나눈 값, 2로 나눈 값, n을 뺀 값의 세 가지 경우에 대해 각각 노드를 생성하여 queue에 삽입 + 노드 생성 시 count 1 증가시키기

- 종료조건을 거치지 않은 경우 -1 반환

import java.util.*;

class Node {
    int number;
    int count;
    
    Node(int number, int count){
        this.number = number;
        this.count = count;
    }
}

class Solution {
    public int solution(int x, int y, int n) {
        int answer = -1;
        
        Queue<Node> queue = new LinkedList<>();        
        queue.offer(new Node(y, 0));

        while(queue.size() > 0){
            Node poll = queue.poll();
            int number = poll.number;
            int count = poll.count;

            if(number == x){
                answer = count;
                break;
            }
            
            if(number % 3 == 0){
                queue.offer(new Node(number / 3, count + 1));
            }
            
            if(number % 2 == 0){
                queue.offer(new Node(number / 2, count + 1));
            }
            
            if(number - n > 0){
                queue.offer(new Node(number - n, count + 1));
            }
        }
        
        return answer;   
    }    
}

Note

- DP로도 많이들 풀었던데 나중에 시도해봐야겠다.