주어진 문자열의 모든 순열을 출력하는 C++ 프로그램

개요

이 문제에서는 하나의 문자열이 주어지며, 우리의 과제는 해당 문자열의 모든 순열(permutation)을 출력하는 프로그램을 작성하는 것입니다.

이 프로그램은 주어진 문자열로 만들 수 있는 가능한 모든 조합을 찾아 화면에 출력합니다.

순열(Permutation)이란 객체의 모든 구성 요소를 가능한 모든 순서로 배열하는 것을 의미합니다.

문제를 더 잘 이해하기 위해 예제를 살펴보겠습니다.

입력

xyz

출력

xyz, xzy, yxz, yzx, zxy, zyx

설명

위 결과는 주어진 문자열의 모든 순열을 순서대로 나열한 것입니다.

문제 해결 접근 방식

이 문제를 해결하기 위해 백트래킹(backtracking) 기법을 사용합니다. 백트래킹이란 문자열의 각 문자를 순열의 첫 번째 문자로 하나씩 지정하고, 그다음 남은 문자들을 순서대로 하나씩 선택해 나가는 방식입니다. 이 과정을 반복하면 문자열의 모든 순열을 얻을 수 있습니다.

구체적인 동작 과정은 다음과 같습니다.

1. 문자열의 왼쪽 끝 인덱스(l)부터 오른쪽 끝 인덱스(r)까지 각 위치의 문자를 현재 위치와 교환(swap)합니다.
2. 교환 후 재귀 호출을 통해 다음 위치로 이동하여 같은 과정을 반복합니다.
3. 재귀 호출이 끝나면 원래 상태로 되돌리기 위해 다시 교환합니다(백트래킹).
4. l == r이 되면 하나의 완성된 순열이 만들어진 것이므로 이를 출력합니다.

주어진 문자열의 모든 순열을 출력하는 프로그램

// 주어진 문자열의 모든 순열을 출력하는 프로그램 −

예제 코드

#include <iostream>
using namespace std;
void findPermutations(string str, int l, int r){
   if (l == r)
   cout<<str<<" ";
   else{
      for (int i = l; i <= r; i++){
         swap(str[l], str[i]);
         findPermutations(str, l+1, r);
         swap(str[l], str[i]);
      }
   }
}
int main(){
   string str = "WXYZ";
   int n = str.size();
   findPermutations(str, 0, n-1);
   return 0;
}

출력 결과

WXYZ WXZY WYXZ WYZX WZYX WZXY XWYZ XWZY XYWZ XYZW XZYW XZWY YXWZ YXZW YWXZ 
YWZX YZWX YZXW ZXYW ZXWY ZYXW ZYWX ZWYX ZWXY

정리

이 프로그램은 길이가 n인 문자열에 대해 n!개의 순열을 생성합니다. 백트래킹을 활용하면 재귀적으로 모든 경우의 수를 체계적으로 탐색할 수 있으며, 문자 교환과 복원 과정을 통해 원본 문자열을 유지하면서 모든 순열을 효율적으로 출력할 수 있습니다.