C++로 풀기: 길이 n인 해피 문자열 중 k번째 사전순 문자열 찾기

해피 문자열(Happy String)이란?

해피 문자열은 다음 두 가지 조건을 동시에 만족하는 문자열입니다.

문자열이 오직 'a', 'b', 'c' 세 문자로만 구성됩니다.
모든 인덱스 i(1 ≤ i ≤ 문자열 길이 − 1)에 대해 s[i] ≠ s[i + 1]을 만족합니다. 즉, 인접한 두 문자가 서로 같지 않아야 합니다.

예를 들어 "abc", "cac", "aba"는 해피 문자열이지만, "aab"처럼 인접한 문자가 반복되거나 'd' 같은 다른 문자가 포함된 문자열은 해피 문자열이 아닙니다.

문제 설명

두 정수 n과 k가 주어졌을 때, 길이가 n인 모든 해피 문자열을 사전순(lexicographical order)으로 정렬한 목록에서 k번째 문자열을 찾는 것이 목표입니다. 만약 길이가 n인 해피 문자열의 개수가 k보다 적다면 빈 문자열을 반환해야 합니다.

예를 들어 n = 3, k = 9라고 가정해 보겠습니다. 길이 3의 해피 문자열은 총 12개이며, 사전순으로 나열하면 다음과 같습니다.

["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"]

이 중 9번째 문자열은 "cab"입니다.

접근 방법: 백트래킹

이 문제는 백트래킹(backtracking) 기법으로 해결할 수 있습니다. 'a', 'b', 'c' 각각으로 시작하는 모든 해피 문자열을 재귀적으로 생성한 뒤, 결과를 정렬하여 k번째 항목을 선택합니다. 단계별 절차는 다음과 같습니다.

생성된 문자열을 저장할 배열 ret을 선언합니다.
solve() 함수를 정의합니다. 이 함수는 현재 문자열 s와 현재 길이 l(초깃값 1)을 매개변수로 받습니다.
l이 목표 길이 x와 같으면 s를 ret의 끝에 추가하고 재귀를 종료합니다.
그렇지 않으면 'a', 'b', 'c' 세 문자를 순회하면서, 현재 문자열의 마지막 문자와 다른 경우에만 해당 문자를 이어 붙여 재귀 호출을 진행합니다.
메인 메서드에서는 x = n으로 설정하고, n이 0이면 빈 문자열을 반환합니다.
solve("a"), solve("b"), solve("c")를 차례로 호출하여 모든 해피 문자열을 생성합니다.
ret을 사전순으로 정렬한 후, k가 배열 크기보다 크면 빈 문자열을, 그렇지 않으면 ret[k - 1]을 반환합니다.

C++ 구현 예제

다음 코드를 통해 구현 과정을 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
char c[3] = {'a', 'b', 'c'};
class Solution {
public:
    vector<string> ret;
    int x;
    void solve(string s, int l = 1){
        if (l == x) {
            ret.push_back(s);
            return;
        }
        for (int i = 0; i < 3; i++) {
            if (s.back() != c[i]) {
                solve(s + c[i], l + 1);
            }
        }
    }
    string getHappyString(int n, int k){
        x = n;
        if (n == 0)
            return "";
        solve("a");
        solve("b");
        solve("c");
        sort(ret.begin(), ret.end());
        return k > ret.size() ? "" : ret[k - 1];
    }
};
main(){
    Solution ob;
    cout << (ob.getHappyString(3,9));
}

입력

3, 9

출력

cab

복잡도 분석

길이가 n인 해피 문자열의 총 개수는 3 × 2ⁿ⁻¹개입니다. 첫 번째 문자는 3가지 선택지가 있고, 이후 각 자리마다 직전 문자와 다른 2가지 문자만 올 수 있기 때문입니다. 따라서 시간 복잡도는 O(3 × 2ⁿ⁻¹)이며, 생성된 모든 문자열을 저장해야 하므로 공간 복잡도 역시 O(3 × 2ⁿ⁻¹)입니다.