C++로 순열 목록에서 누락된 순열 찾기

문제 정의

임의의 단어에 대한 여러 순열이 담긴 목록이 주어집니다. 이 목록에서 빠져 있는(누락된) 순열을 찾아내는 것이 과제입니다.

예시

순열 목록 = { "ABC", "ACB", "BAC", "BCA" } 라면,
누락된 순열은 { "CBA", "CAB" } 입니다.

알고리즘

• 주어진 모든 문자열을 포함하는 집합(set)을 생성합니다.
• 가능한 모든 순열을 포함하는 또 하나의 집합을 생성합니다.
• 두 집합의 차집합을 구하여 반환합니다.

구현 예시

#include <bits/stdc++.h>
using namespace std;
void findMissingPermutation(string givenPermutation[], size_t
permutationSize) {
   vector<string> permutations;
   string input = givenPermutation[0];
   permutations.push_back(input);
   while (true) {
      string p = permutations.back();
      next_permutation(p.begin(), p.end());
      if (p == permutations.front())
         break;
      permutations.push_back(p);
   }
   vector<string> missing;
   set<string> givenPermutations(givenPermutation,
   givenPermutation + permutationSize);
   set_difference(permutations.begin(), permutations.end(),
      givenPermutations.begin(),
      givenPermutations.end(),
      back_inserter(missing));
   cout << "Missing permutations are" << endl;
   for (auto i = missing.begin(); i != missing.end(); ++i)
      cout << *i << endl;
}
int main() {
   string givenPermutation[] = {"ABC", "ACB", "BAC", "BCA"};
   size_t permutationSize = sizeof(givenPermutation) / sizeof(*givenPermutation);
   findMissingPermutation(givenPermutation, permutationSize);
   return 0;
}

코드 설명

위 코드는 C++ STL의 next_permutation 함수를 핵심적으로 활용합니다. 먼저 첫 번째 문자열을 기준으로 삼은 뒤, 사전순으로 다음 순열을 반복해서 생성합니다. 생성된 순열이 다시 첫 번째 문자열로 돌아오면 가능한 모든 순열을 만든 것이므로 반복을 종료합니다. 이후 set_difference 알고리즘을 사용해 전체 순열 집합에서 주어진 순열 집합에 포함되지 않은 원소, 즉 누락된 순열만 추출하여 출력합니다.

참고로 next_permutation이 모든 순열을 올바르게 생성하려면 입력 문자열이 오름차순으로 정렬되어 있어야 하며, 위 예제의 "ABC"처럼 이미 정렬된 상태여야 합니다.

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

출력

Missing permutations are
CAB
CBA