[programmers] 숫자 변환하기 - Java

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

숫자 변환하기

문제 설명

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.
  • x에 n을 더합니다
  • x에 2를 곱합니다.
  • x에 3을 곱합니다.
자연수 xyn이 매개변수로 주어질 때, 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를 이용해 문제를 해결하는 법을 익힐 수 있었다.
 
Share article

More articles

See more posts

👨🏻‍💻DriedPollack's Blog