Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++에서 vector(ArrayList)를 활용해 문자열의 모든 부분 수열 출력하기

C++ 프로그래밍에서는 하나의 문자열이 주어졌을 때, 그 문자열로 만들 수 있는 모든 부분 수열(subsequence)을 출력해야 하는 경우가 많습니다. 부분 수열은 문자열에서 0개 이상의 문자를 제거하여 얻을 수 있으며, 남은 문자들은 반드시 원래 순서를 유지해야 한다는 점이 중요합니다.

먼저 예제를 통해 문제를 더 명확히 이해해 보겠습니다.

입력: str = "xyz"
출력: x y xy z xz yz xyz

접근 방식: 재귀와 동적 배열

이 문제를 해결하는 가장 직관적인 방법은 재귀 호출을 활용하는 것입니다. 문자열의 각 문자를 앞에서부터 차례대로 확인하며, 매 단계마다 두 가지 선택지가 존재합니다.

  • 현재 문자를 부분 수열에 포함하지 않고 다음 문자로 진행
  • 현재 문자를 부분 수열에 포함한 후 다음 문자로 진행

문자열의 끝에 도달하면 하나의 부분 수열이 완성되며, 이렇게 만들어진 결과들을 C++의 동적 배열 컨테이너인 std::vector(자바의 ArrayList에 해당)에 저장했다가 마지막에 한 번에 출력하면 됩니다. 길이가 n인 문자열은 최대 2n개의 부분 수열을 가질 수 있으므로, 전체 시간 복잡도는 O(2n)입니다.

C++ 구현 코드

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// 재귀적으로 모든 부분 수열을 생성하는 함수
void generateSubsequences(const string& str, int index,
                          string current, vector<string>& result) {
    // 문자열 끝에 도달하면 지금까지 만든 부분 수열을 저장
    if (index == (int)str.size()) {
        if (!current.empty()) {   // 빈 문자열은 제외
            result.push_back(current);
        }
        return;
    }

    // 1) 현재 문자를 포함하지 않는 경우
    generateSubsequences(str, index + 1, current, result);

    // 2) 현재 문자를 포함하는 경우
    generateSubsequences(str, index + 1, current + str[index], result);
}

int main() {
    string str = "xyz";
    vector<string> subsequences;

    generateSubsequences(str, 0, "", subsequences);

    cout << "모든 부분 수열:" << endl;
    for (const auto& sub : subsequences) {
        cout << sub << " ";
    }
    return 0;
}

실행 결과

모든 부분 수열:
z y yz x xz xy xyz

길이가 3인 문자열 "xyz"로 만들 수 있는 비어 있지 않은 부분 수열은 총 7개(23 − 1개)입니다. 이 접근 방식은 자바 등 다른 언어에서도 동일하게 적용할 수 있으며, 자바에서는 ArrayList<String>을 사용해 똑같은 로직을 구현하면 됩니다.