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

문제 설명

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

프로그래머스

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

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

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return 하도록 solution 함수를 완성해 주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

제한 사항

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

입출력 예

x	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

입출력 예 설명

입출력 예 #1

• x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #2

• x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #3

• x를 y로 변환할 수 없기 때문에 -1을 return합니다.

 

내가 작성한 코드

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        // 연산값과 연산 횟수를 저장할 Queue 생성
        Queue<int[]> queue = new LinkedList<>();
        // 연산값의 중복을 방지할 boolean 배열 생성, y를 넘는 숫자는 확인할 필요가 없음
        boolean[] visited = new boolean[y + 1];
        
        // [현재 숫자, 연산 횟수]
        queue.add(new int[]{x, 0});
        visited[x] = true;
        
        // 연산 반복 진행
        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            // 현재 숫자
            int num = now[0];
            // 연산 횟수
            int count = now[1];
            
            // 목표 숫자 도달 시 종료
            if (num == y) {
                return count;
            }
            
            // 다음 단계 가능한 연산들
            int[] next = {num + n, num * 2, num * 3};
            
            for (int nxt : next) {
                // y를 넘지 않고 방문하지 않은 경우만 탐색 진행
                if (nxt <= y && !visited[nxt]) {
                    visited[nxt] = true;
                    queue.add(new int[]{nxt, count + 1});
                }
            }
        }
        
        // y에 도달 불가능한 경우 -1
        return -1;
    }
}

문제를 풀기 위해 생각한 방향

처음 문제를 봤을 때, 주어진 정수 x를 시작으로 +n, *2, *3 세 가지 연산을 통해 목표 숫자 y를 만드는 최소 연산 횟수를 구하는 문제라는 점을 파악했다. 처음에는 y에서 x로 거꾸로 줄여가는 방식으로 접근해보려 했다. 예를 들어 y에서 n을 빼거나, 2 또는 3으로 나누면서 x가 될 수 있는지 확인하는 식이다. 하지만 이렇게 역방향으로 탐색하면 경우의 수가 기하급수적으로 늘어나고, 나누어 떨어지지 않는 경우가 많아 막히는 지점이 생기기 때문에 비효율적이라고 판단했다.

이에 반해 x에서 y로 가는 정방향 탐색은 연산이 단순하고, “최소 연산 횟수”를 찾는 데 적합하다고 생각했다. 특히 BFS(너비 우선 탐색)를 사용하면, 한 단계씩 가능한 모든 연산을 탐색하기 때문에 가장 먼저 y에 도달하는 순간이 곧 최소 횟수라는 점에서 효율적이다.

구현은 Queue를 사용하여 (현재 숫자, 연산 횟수) 형태로 저장하고, 매 단계마다 +n, *2, *3을 수행해 새로운 숫자를 큐에 넣었다. 이미 방문한 숫자는 boolean[] visited로 관리하여 중복 탐색을 막았다. 또한, 탐색 도중 num == y가 되는 순간 바로 return count;로 종료해 최단 거리를 보장하도록 했다.

결과적으로 이 문제는 단순한 수식 계산이 아니라, 가능한 연산 경로 중 최소 이동 횟수를 찾는 그래프 탐색 문제로 접근해야 하며, BFS를 통해 효율적으로 해결할 수 있다는 점이 핵심이었다.