[programmers] 숫자 변환하기 - Java

자연수 x를 y로 변환하기 위한 최소 연산 횟수를 구하는 문제로, 가능한 연산은 n을 더하는 것과 2 또는 3을 곱하는 것입니다. BFS를 사용하여 현재 값과 연산 횟수를 저장하고, 중복 계산을 피하기 위해 방문 배열을 활용합니다. 주어진 예제에 따라 변환이 불가능할 경우 -1을 반환합니다.

DriedPollack

Nov 01, 2024

Contents

숫자 변환하기 solution.java 핵심 키워드 결론!

숫자 변환하기

문제 설명

자연수 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합니다.

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를 수행한다.

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

결론!

해당 문제를 통해 BFS를 이용해 문제를 해결하는 법을 익힐 수 있었다.