C++로 정렬된 순서에서 N번째 이진 문자열 찾기

이 문제에서는 양의 정수 N이 주어지며, 우리의 목표는 정렬된 순서에서 N번째 이진 문자열을 찾는 것입니다.

즉, 두 개의 문자 a와 b만으로 만들 수 있는 무한한 문자열 목록에서 사전순(lexicographical order)으로 정렬했을 때 N번째에 해당하는 문자열을 구해야 합니다.

해당 문자열 목록은 다음과 같습니다.

a, b, aa, ab, ba, bb, aaa, aab, aba, …

문제 이해를 위한 예시

입력 : N = 8
출력 : aab

해결 접근 방법

가장 단순한 해결 방법은 반복문을 사용하여 모든 문자열을 처음부터 생성한 뒤, 그중 N번째 문자열을 반환하는 것입니다. 이 방법으로도 문제를 해결할 수 있지만, N의 값이 커질 경우 비효율적이라는 한계가 있습니다.

따라서 더 적은 시간 안에 답을 구할 수 있는 다른 방법을 살펴보겠습니다.

더 효율적인 접근 방식은 문자열의 상대 인덱스(relative index)를 활용하는 것입니다. 길이가 L인 문자열은 2개의 기호로 2^L개를 만들 수 있다는 사실을 이용하면, 상대 인덱스를 통해 해당 문자열의 이진수 형태를 바로 찾을 수 있습니다.

상대 인덱스는 다음 공식으로 계산합니다.

상대 인덱스 = N + 1 − 2^{⌊log₂(N+1)⌋}

여기서 상대 인덱스를 이진수로 변환한 뒤, 각 비트가 0이면 'a', 1이면 'b'로 치환하면 원하는 문자열을 얻을 수 있습니다.

구현 예제

다음은 위에서 설명한 솔루션의 동작을 보여주는 C++ 프로그램입니다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int

string findBinString(ll n){
    ll len = (int)log2(n + 1);
    int ri = n + 1 - pow(2, len);
    ll i = 0;
    string binString = "";
    for (i = 0; i < len; i++) {
        binString += 'a';
    }
    i = 0;
    while (ri > 0) {
        if (ri % 2 == 1)
            binString[i] = 'b';
        ri /= 2;
        i++;
    }
    reverse(binString.begin(), binString.end());
    return binString;
}

int main(){
    ll n = 245;
    cout<<"The "<<n<<"-th binary string in sorted order is "<<findBinString(n);
    return 0;
}

출력 결과

The 245-th binary string in sorted order is bbbabba

코드 설명

위 코드의 동작 과정을 단계별로 살펴보면 다음과 같습니다.

먼저 log₂(N+1)의 정수 부분을 구해 목표 문자열의 길이(len)를 결정합니다. 그다음 상대 인덱스(ri)를 계산하고, 문자열을 길이만큼 'a'로 초기화합니다. 이후 상대 인덱스를 이진수로 변환하면서 각 비트가 1인 자리를 'b'로 바꿔줍니다. 마지막으로 문자열을 뒤집으면 사전순으로 정렬된 N번째 문자열이 완성됩니다.

이 방법은 반복문으로 모든 문자열을 생성하는 O(N) 방식과 달리, 로그 시간 내에 결과를 구할 수 있어 N이 매우 큰 경우에도 효율적으로 동작합니다.