[programmers] 숫자 변환하기 - Java

숫자 변환하기

문제 설명

• x에 n을 더합니다

• x에 2를 곱합니다.

• x에 3을 곱합니다.

제한사항

• 1 ≤ x ≤ y ≤ 1,000,000

• 1 ≤ n < y

입출력 예

입출력 예 설명

solution.java

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        if (x == y) return 0;

        Queue<int[]> queue = new LinkedList<>();
        boolean[] visited = new boolean[y + 1];
        queue.add(new int[]{x, 0});  // x의 현재 값과 연산 횟수 저장
        visited[x] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int currentValue = current[0];
            int operations = current[1];

            // 가능한 작업들 시도
            int[] nextValues = {currentValue + n, currentValue * 2, currentValue * 3};

            for (int nextValue : nextValues) {
                if (nextValue == y) {
                    return operations + 1;
                }
                if (nextValue < y && !visited[nextValue]) {
                    queue.add(new int[]{nextValue, operations + 1});
                    visited[nextValue] = true;
                }
            }
        }

        return -1;  // y로 만들 수 없는 경우
    }
}

핵심 키워드

• 큐를 사용하여 현재 값과 이에 도달하기 위해 수행된 작업 수를 저장한다.

• 현재 값에 대해 가능한 각 연산(n 더하기, 2 곱하기, 3 곱하기)을 검사하여 BFS를 수행한다.

• 중복 계산과 무한 루프를 피하기 위해 '방문' 배열을 사용하여 이미 처리한 값을 표시한다.

결론!