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

C++로 구현하는 조합 반복자(Combination Iterator)

문제 개요

조합(Combination)을 순차적으로 탐색할 수 있는 반복자(Iterator) 클래스를 설계해야 합니다. 이 클래스는 다음과 같은 연산을 제공해야 합니다.

  • 생성자: 정렬되어 있고 중복 없는 소문자 영어 알파벳으로 구성된 문자열과 숫자 combinationLength를 매개변수로 받습니다.
  • next(): 알파벳 순서를 기준으로 길이가 combinationLength인 다음 조합을 반환합니다.
  • hasNext(): 다음 조합이 존재하는 경우에만 true를 반환하고, 그렇지 않으면 false를 반환합니다.

예를 들어 입력이 다음과 같다고 가정해 보겠습니다.

CombinationIterator iterator = new CombinationIterator("xyz", 2);
iterator.next(); // "xy" 반환
iterator.hasNext(); // true 반환
iterator.next(); // "xz" 반환
iterator.hasNext(); // true 반환
iterator.next(); // "yz" 반환
iterator.hasNext(); // false 반환

풀이 접근 방법

이 문제는 재귀적으로 모든 조합을 미리 생성해 두고, 포인터를 이용해 하나씩 꺼내는 방식으로 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.

  • 문자열 배열 comb와 인덱스 변수 idx를 준비합니다.
  • makeCombs() 메서드를 정의합니다. 이 메서드는 문자열 s, 정수 l, 초기값이 빈 문자열인 temp, 그리고 초기값이 0인 start를 매개변수로 받으며, 동작은 다음과 같습니다.
    • temp의 길이가 l과 같으면 temp를 comb에 추가하고 종료합니다.
    • i를 start부터 문자열 s의 길이까지 반복하면서 makeCombs(s, l, temp + s[i], i + 1)을 재귀 호출합니다.
  • printVector() 메서드는 문자열 배열을 입력받아 각 요소를 화면에 출력합니다.
  • 생성자는 문자열 c와 정수 cl을 받아 makeCombs(c, cl)을 호출한 뒤, idx를 0으로 초기화합니다.
  • next() 메서드는 idx를 1 증가시킨 후 comb[idx - 1]을 반환합니다.
  • hasNext() 메서드는 idx가 comb의 크기와 같지 않으면 true를, 같으면 false를 반환합니다.

C++ 구현 예제

아래 구현 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class CombinationIterator {
public:
   vector <string> combs;
   int idx;
   void makeCombs(string s, int l, string temp ="", int start = 0){
      if(temp.size() == l){
         combs.push_back(temp);
         return;
      }
      for(int i = start; i < s.size(); i++){
         makeCombs(s, l, temp + s[i], i + 1);
      }
   }
   void printVector(vector <string> v){
      for(int i = 0; i < v.size(); i++){
         cout << v[i] << "\n";
      }
      cout << endl;
   }
   CombinationIterator(string c, int cl) {
      makeCombs(c, cl);
      idx = 0;
   }
   string next() {
      idx++;
      return combs[idx - 1];
   }
   bool hasNext() {
      return !(idx == combs.size());
   }
};
main(){
   CombinationIterator ob("xyz", 2);
   cout << (ob.next()) << endl;
   cout << (ob.hasNext()) << endl;
   cout << (ob.next()) << endl;
   cout << (ob.hasNext()) << endl;
   cout << (ob.next()) << endl;
   cout << (ob.hasNext()) << endl;
}

입력

"xyz"와 2로 초기화한 뒤, next()와 hasNext()를 여러 번 호출

출력

xy
1
xz
1
yz
0

동작 원리 정리

이 구현의 핵심은 전처리(pre-processing) 방식입니다. 생성자가 호출될 때 재귀 함수 makeCombs()가 가능한 모든 조합을 이미 사전순으로 배열에 저장해 둡니다. 이후 next()와 hasNext()는 단순히 인덱스를 증가시키거나 범위를 확인하는 O(1) 연산만 수행하므로, 반복 조회가 잦은 상황에서 효율적입니다. 다만 문자열 길이가 길어지면 조합의 개수가 지수적으로 늘어나므로, 메모리 사용량을 고려해야 한다는 점을 유의하세요.