개요
이 튜토리얼에서는 k번째 붐 넘버(k-th Boom Number)를 찾는 C++ 프로그램을 작성해 보겠습니다.
여기서 붐 넘버(Boom Number)란 숫자 2와 3으로만 구성된 수를 의미합니다. 예를 들어 2, 3, 22, 23, 32, 33, 222처럼 각 자릿수가 2 또는 3으로만 이루어진 수들이 모두 붐 넘버에 해당합니다.
문제 해결 접근 방식
붐 넘버는 2와 3으로만 이루어져 있으므로, 큐(queue)를 활용한 BFS(너비 우선 탐색) 방식으로 차례대로 생성할 수 있습니다. 문제를 해결하는 단계는 다음과 같습니다.
- k 값을 초기화합니다.
- 문자열을 저장할 큐를 초기화합니다.
- 빈 문자열("")을 큐에 삽입합니다.
- 카운터 변수를 0으로 초기화합니다.
- 카운터가 주어진 k보다 작거나 같은 동안 반복하는 루프를 작성합니다.
- 큐의 맨 앞(front) 요소를 가져옵니다.
- 해당 요소를 큐에서 제거(pop)하고 변수에 저장합니다.
- 저장한 문자열 뒤에 '2'를 덧붙인 수를 큐에 삽입합니다.
- 카운터를 증가시키고, 카운터가 k와 같다면 해당 값을 출력하고 반복을 종료합니다.
- 같은 방식으로 저장한 문자열 뒤에 '3'을 덧붙인 수를 큐에 삽입합니다.
- 카운터를 증가시키고, 카운터가 k와 같다면 해당 값을 출력하고 반복을 종료합니다.
이 방식은 자릿수가 짧은 붐 넘버부터, 같은 길이 안에서는 앞자리 숫자 순서대로(사전 순) 생성되기 때문에 k번째 붐 넘버를 정확하게 찾을 수 있습니다.
예제 코드
위 알고리즘을 C++ 코드로 구현하면 다음과 같습니다.
#include<bits/stdc++.h>
using namespace std;
void findKthBoomNumber(long long k) {
queue<string> queue;
queue.push("");
long long count = 0;
while (count <= k) {
string numberOne = queue.front();
queue.pop();
string numberTwo = numberOne;
queue.push(numberOne.append("2"));
count++;
if (count == k) {
cout << numberOne << endl;
break;
}
queue.push(numberTwo.append("3"));
count++;
if (count == k) {
cout << numberTwo << endl;
break;
}
}
}
int main() {
long long k = 45;
findKthBoomNumber(k);
return 0;
}
코드 설명
findKthBoomNumber함수는 k번째 붐 넘버를 찾아 출력하는 역할을 합니다.- 빈 문자열부터 시작하여, 매 반복마다 현재 문자열 뒤에 '2' 또는 '3'을 덧붙인 새로운 후보 수를 큐에 추가함으로써 모든 붐 넘버를 순차적으로 생성합니다.
- 카운터가 정확히 k에 도달하는 순간 그 숫자를 출력하고 루프를 종료합니다.
실행 결과
위 코드를 실행하면 k = 45일 때 다음과 같은 결과가 출력됩니다.
23332
즉, 45번째 붐 넘버는 23332입니다.
시간 복잡도
이 알고리즘은 한 번의 반복마다 두 개의 새로운 숫자를 생성하므로 시간 복잡도는 O(k)입니다. 따라서 k가 커져도 선형 시간 안에 효율적으로 답을 구할 수 있습니다.
마무리
지금까지 큐를 활용해 k번째 붐 넘버를 찾는 방법을 단계별로 살펴보았습니다. 이 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.