C++로 n개 문자 집합에서 만들 수 있는 길이 k의 모든 문자열 출력하기

문제 개요

이 문제에서는 하나의 문자 집합(set)과 양의 정수 k가 주어집니다. 우리가 해야 할 일은 해당 집합의 문자들을 사용하여 만들 수 있는 길이 k의 모든 가능한 문자열을 출력하는 것입니다.

예시를 통해 문제를 더 자세히 살펴보겠습니다.

입력: set = {'x', 'y', 'z'}, k = 2
출력: xx, xy, xz, yx, yy, yz, zx, zy, zz

접근 방법

이 문제를 해결하려면 집합의 문자들로 생성할 수 있는 모든 가능한 시퀀스를 찾아야 합니다.

핵심 아이디어는 다음과 같습니다.

• 크기가 n인 집합에서 만들 수 있는 길이 k의 문자열 총 개수는 n^k개입니다.
• 빈 문자열("")에서 시작합니다.
• 재귀 호출을 통해 문자를 하나씩 붙여 나갑니다.
• 길이가 k에 도달하면 완성된 문자열을 출력하고 재귀를 종료합니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;

void printKLengthString(char set[], string sequence, int n, int k) {
    if (k == 0){
        cout << sequence << "\t";
        return;
    }
    for (int i = 0; i < n; i++){
        string newSequence;
        newSequence = sequence + set[i];
        printKLengthString(set, newSequence, n, k - 1);
    }
}

int main() {
    char set[] = {'a', 'b'};
    int n = 2;
    int k = 3;
    printKLengthString(set, "", n, k);
}

실행 결과

aaa  aab  aba  abb  baa  bab  bba  bbb

동작 원리

위 코드에서는 각 재귀 단계마다 현재까지 만들어진 문자열(sequence)에 집합의 모든 문자를 차례로 하나씩 추가하며 새로운 문자열을 만듭니다. 남은 길이(k)가 0이 되면 더 이상 문자를 추가할 필요가 없으므로 완성된 문자열을 출력하고 재귀 호출을 종료합니다.

예를 들어 집합 {'a', 'b'}와 k = 3이 주어지면, 전체 문자열의 개수는 2³ = 8개이며, 위 실행 결과처럼 aaa부터 bbb까지 중복을 허용한 모든 조합이 출력됩니다.