이 문제에서 양수 1이 주어집니다. 우리의 임무는 정렬된 순서로 N번째 바이너리 문자열을 찾는 것입니다.
사전순으로 정렬된 두 개의 기호 a와 b만 사용하여 생성된 무한 문자열 목록에서 N번째 문자열을 찾아야 합니다.
목록은 -
a, b, aa, ab, ba, bb, aaa, aab, aba, …
문제를 이해하기 위해 예를 들어보겠습니다.
Input : N = 8 Output : aab
해결 방법
문제에 대한 간단한 해결책은 루프를 사용하여 모든 n개의 문자열을 생성하는 것입니다. 그런 다음 N번째 문자열을 반환합니다. 이 솔루션은 작업을 수행하지만 N 값이 큰 경우 효과적인 솔루션을 제공할 수 없습니다.
따라서 더 짧은 시간에 솔루션을 제공할 수 있는 또 다른 솔루션을 보게 될 것입니다.
문제를 해결하는 또 다른 방법은 문자열에 대한 상대 인덱스를 사용하는 것입니다. 길이가 N인 스트링의 개수는 2개의 심볼을 사용하여 생성할 수 있다는 사실을 사용하면 2N입니다. 상대 색인을 사용하여 이진 형식을 찾을 수 있습니다. 문자열.
상대 지수 =N + 1 - 2( floor(log(N+1)) )
예
솔루션 작동을 설명하는 프로그램
#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