Programmers | Level 2 | 숫자 변환하기
Programmers | Level 2 | 숫자 변환하기
Problems
- 📘 Src: Programmers
- 🗂️ Cat: Breadth-First Search
Description
자연수 x를 y로 변환하기 위해 필요한 최소 연산 횟수를 구하는 문제입니다. 사용할 수 있는 연산은 다음 세 가지입니다:
x에n을 더합니다.x에 2를 곱합니다.x에 3을 곱습니다.
이 연산들을 사용해 x에서 y로 변환할 수 있는지 확인하고, 최소 몇 번의 연산으로 변환할 수 있는지를 구하는 문제입니다. 변환이 불가능할 경우 -1을 반환해야 합니다.
Constraints
- 1 ≤
x≤y≤ 1,000,000 - 1 ≤
n<y
Examples
| x | y | n | result |
|---|---|---|---|
| 10 | 40 | 5 | 2 |
| 10 | 40 | 30 | 1 |
| 2 | 5 | 4 | -1 |
Solutions
Code
import java.util.*;
class Solution {
public int solution(int x, int y, int n) {
Deque<int[]> queue = new LinkedList<>(); // BFS를 위한 큐 초기화 [숫자, 연산 횟수]
boolean[] visited = new boolean[y + 1]; // 방문한 숫자 기록하는 배열 초기화
// 시작 숫자와 초기 연산 횟수
queue.add(new int[]{x, 0});
visited[x] = true;
// BFS 탐색 시작
while (!queue.isEmpty()) {
int[] current = queue.poll();
int number = current[0]; // 현재 숫자
int count = current[1]; // 현재 연산 회수
// x → y 도달한 경우 최소 연산 횟수 반환
if (number == y) return count;
// 가능한 다음 연산 (x + n, x * 2, x * 3)
int[] nextNumbers = new int[]{number + n, number * 2, number * 3};
for (int next : nextNumbers) {
// y를 넘지 않으면서 방문하지 않은 숫자만 탐색
if (next <= y && !visited[next]) {
visited[next] = true; // 방문 기록
queue.add(new int[]{next, count + 1}); // 큐에 추가
}
}
}
// 변환이 불가능한 경우 -1 반환
return -1;
}
}
Approach
이 문제는 자연수 x를 y로 변환하는 데 필요한 최소 연산 횟수를 구하는 BFS(너비 우선 탐색) 문제입니다. BFS는 최단 경로 탐색에 적합하며, 이 문제는 x에서 시작해 목표 값 y에 도달하는 최단 경로를 찾는 문제로 볼 수 있습니다. 다음과 같은 방식으로 문제를 해결하였습니다.
1. BFS를 사용한 이유
BFS는 모든 경로를 동일한 깊이로 탐색한 후, 다음 깊이로 넘어가므로 x에서 y로 변환하는 최단 경로를 보장합니다. 각 숫자는 그래프의 노드로 간주할 수 있으며, 가능한 연산은 노드 간의 간선으로 볼 수 있습니다. BFS를 사용하면 각 단계에서 가능한 모든 연산을 시도하여 목표 값 y에 도달하는 최단 경로를 찾을 수 있습니다.
2. BFS 초기 설정
우선 BFS 탐색을 위한 큐를 준비하고, 시작점으로 숫자 x와 연산 횟수 0을 큐에 넣습니다. 방문한 숫자를 기록하는 배열을 사용하여 중복된 숫자를 여러 번 탐색하지 않도록 설정하였습니다. 이 방문 배열은 x부터 y까지의 숫자를 추적하며, 이미 방문한 숫자는 다시 탐색하지 않도록 처리합니다.
Deque<int[]> queue = new LinkedList<>();
queue.add(new int[]{x, 0}); // 시작 숫자 x와 연산 횟수 0을 큐에 추가
boolean[] visited = new boolean[y + 1]; // 방문 체크 배열 생성
visited[x] = true; // 초기 숫자 x는 방문 처리
3. BFS 탐색 과정
BFS는 큐에서 숫자와 연산 횟수를 하나씩 꺼내서 다음 가능한 상태로 전이하는 방식으로 동작합니다. 문제에서 주어진 세 가지 연산 x + n, x * 2, x * 3을 각각 적용하고, 그 결과가 목표 값 y보다 작거나 같으며 아직 방문하지 않은 상태라면 큐에 추가합니다.
이 과정에서 목표 값 y에 도달하면 그때까지의 연산 횟수를 반환하며, 이 값이 최소 연산 횟수가 됩니다. 만약 목표 값에 도달하지 못하고 모든 가능한 상태를 탐색했다면 변환이 불가능하다는 의미로 -1을 반환합니다.
먼저, 큐에서 현재 상태를 꺼내옵니다. BFS의 특성상 먼저 꺼낸 상태가 가장 적은 연산을 사용해 도달한 상태입니다. number는 현재 상태의 숫자이고, count는 해당 숫자에 도달하기까지의 연산 횟수입니다.
while (!queue.isEmpty()) { // 모든 경우의 수 탐색 종료 시까지 탐색
int[] current = queue.poll();
int number = current[0]; // 현재 숫자
int count = current[1]; // 현재 연산 횟수
...
}
만약, 현재 숫자가 목표 숫자 y와 같다면, 더 이상 탐색할 필요가 없으므로 현재까지의 연산 횟수 count를 반환합니다. BFS의 특성상 이 값이 곧 최소 연산 횟수입니다.
// x → y 도달한 경우 최소 연산 횟수 반환
if (number == y) return count;
현재 숫자에서 가능한 세 가지 연산 x + n, x * 2, x * 3을 모두 시도합니다. 각 연산의 결과가 y보다 작거나 같고, 아직 방문하지 않은 숫자라면 그 숫자를 큐에 추가하고 방문 여부를 기록합니다. 이로써 중복 탐색을 방지하고, 다음 탐색 대상으로 넘깁니다.
// 가능한 다음 연산 (x + n, x * 2, x * 3)
int[] nextNumbers = new int[]{number + n, number * 2, number * 3};
for (int next : nextNumbers) {
// y를 넘지 않으면서 방문하지 않은 숫자만 탐색
if (next <= y && !visited[next]) {
visited[next] = true; // 방문 기록
queue.add(new int[]{next, count + 1}); // 큐에 추가
}
}
4. 변환이 불가능한 경우
만약 BFS 탐색을 종료한 후에도 목표 값 y에 도달하지 못했다면, 이는 변환이 불가능한 경우입니다. 이때는 -1을 반환하여 문제에서 요구하는 조건을 만족시킵니다.
// 목표 숫자에 도달하지 못한 경우 -1 반환
return -1;
Complexity
- ⏳ TC: O(n)
- 💾 SC: O(n)
시간 및 공간 복잡도는 모두 O(n)입니다. 이 알고리즘은 BFS를 사용하여 숫자 x에서 y까지의 모든 숫자를 한 번씩만 탐색합니다. 각 숫자는 세 가지 연산을 통해 다음 상태로 전이되며, 탐색이 최대 y까지 진행됩니다. 각 숫자는 큐에 한 번씩 들어가고, 방문 배열에 의해 중복되지 않으므로, 탐색 시간은 y에 비례해 O(n)의 시간 복잡도를 가집니다. 또한, BFS 탐색을 위해 큐와 방문 배열을 사용하므로 큐는 최대 y까지의 숫자를 저장할 수 있고, 방문 배열도 y까지의 숫자를 추적합니다. 따라서 공간 복잡도 또한 O(n)입니다.
- Algorithm
- Breadth-First Search