이 문제에서는 숫자 N이 주어지며, 이 숫자를 'A'와 'B'로만 구성된 문자열 형태로 사전순(lexicographic order)에 맞게 출력하는 프로그램을 작성하는 것이 목표입니다.
문제 이해하기
모든 숫자는 다음과 같은 규칙으로 'A'와 'B'의 조합으로 표현할 수 있습니다.
1 = A 2 = B 3 = AA 4 = AB 5 = BA 6 = BB 7 = AAA 8 = AAB
규칙을 보면 마치 이진수를 세듯이 'A'가 0, 'B'가 1 역할을 하는 것과 유사하다는 것을 알 수 있습니다.
입력 및 출력 예시
- 입력: N = 12
- 출력: BAB
풀이 접근 방법
'A'와 'B'로 이루어진 문자열은 사실상 이진수와 동일한 구조를 가집니다. 문자열을 찾기 위해서는 먼저 문자열의 길이를 구해야 합니다. 길이별로 표현 가능한 숫자의 개수를 활용하면 됩니다.
- 길이 1인 문자열은 2개 (숫자 1~2까지)
- 길이 2인 문자열은 4개 (숫자 3~6까지)
- 길이 3인 문자열은 8개 (숫자 7~14까지)
길이를 찾은 후에는 문자열의 각 자리 문자를 결정해야 합니다. 문자를 하나씩 추가하면서 남은 길이를 갱신하는 방식으로 반복 처리합니다. 각 자리의 문자는 N과 2^남은길이 값을 비교하여 결정됩니다. N이 해당 값보다 작으면 현재 문자는 'A', 그렇지 않으면 'B'입니다. 매 반복마다 길이를 1씩 줄이며, 만약 문자가 'B'로 결정되었다면 N에서 해당 값을 빼서 갱신합니다.
구현 예제 코드
#include <iostream>
#include<math.h>
using namespace std;
int findStringLength(int M) {
int stringLen = 1;
while((pow(2, stringLen + 1) - 2) < M) {
stringLen++;
}
return stringLen;
}
void printNumString(int N) {
int stringLen, num, stringNumber;
stringLen = findStringLength(N);
stringNumber = N - (pow(2, stringLen) - 2);
while (stringLen) {
num = pow(2, stringLen - 1);
if (num < stringNumber) {
cout<<"B";
stringNumber -= num;
}
else {
cout<<"A";
}
stringLen--;
}
}
int main() {
int N = 47;
cout<<"The number as sting of 'A' and 'B' in lexicographic order is ";
printNumString(N);
return 0;
}
실행 결과
The number as sting of 'A' and 'B' in lexicographic order is BAAAA
코드 동작 원리 정리
findStringLength 함수는 주어진 숫자 M을 표현하는 데 필요한 최소 문자열 길이를 계산합니다. 2^(길이+1) - 2가 M보다 작은 동안 길이를 늘려가며, 누적 표현 범위 안에 들어오는 길이를 반환합니다.
printNumString 함수는 전체 범위에서 해당 길이 시작 지점(2^길이 - 2)을 뺀 상대적 위치를 계산한 뒤, 각 자리마다 2^(남은길이-1) 값과 비교하여 'A' 또는 'B'를 결정하고 출력합니다. 시간 복잡도는 O(log N)으로 매우 효율적으로 동작합니다.