C++에서 순열 찾기 – 스택으로 사전순 최소 순열 구하기

문제 소개

문자 'D'와 'I'로만 이루어진 비밀 시그니처(secret signature)가 주어졌다고 가정해 봅시다. 'D'는 두 숫자 사이의 감소 관계를, 'I'는 증가 관계를 의미합니다. 이 시그니처는 1부터 n까지의 서로 다른 숫자를 모두 한 번씩 사용하는 특별한 정수 배열로부터 생성됩니다.

예를 들어 시그니처 "DI"는 [2, 1, 3] 또는 [3, 1, 2]와 같은 배열로 만들 수 있습니다. 반면 [3, 2, 4]나 [2, 1, 3, 4] 같은 배열로는 만들 수 없는데, 이 배열들은 "DI" 시그니처를 표현할 수 없는 잘못된 조합이기 때문입니다.

목표: 사전순으로 가장 작은 순열 찾기

우리가 구해야 하는 것은 주어진 비밀 시그니처를 만족하는 [1, 2, ..., n]의 순열 중에서 사전순(lexicographical order)으로 가장 작은 순열입니다.

예를 들어 입력이 "DI"라면 출력은 [2, 1, 3]이 됩니다. [3, 1, 2] 역시 "DI"를 만족하지만, 사전순으로 더 작은 [2, 1, 3]을 선택해야 합니다.

알고리즘 접근 방법

이 문제는 스택(stack) 자료구조를 활용하면 선형 시간 안에 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 감소 구간('D')을 만나면 해당 숫자들을 스택에 쌓아두었다가, 증가 지점('I')에서 역순으로 꺼내 배치하는 것입니다. 단계별 과정은 다음과 같습니다.

스택 st를 하나 정의합니다.
결과를 저장할 정수 벡터 ret을 정의합니다.
i를 1부터 문자열 s의 길이까지 1씩 증가시키며 반복합니다.
- s[i - 1]이 'D'인 경우: i를 스택 st에 push합니다.
- 그 외의 경우('I'인 경우): i를 ret의 끝에 추가한 뒤, 스택이 빌 때까지 st의 top 요소를 ret 끝에 추가하면서 pop합니다.
반복문이 종료되면 s.size() + 1을 스택에 push합니다.
스택이 빌 때까지 top 요소를 ret에 추가하며 pop합니다.
ret을 반환합니다.

C++ 구현 예제

아래 구현 예제를 통해 더 쉽게 이해할 수 있습니다.

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

void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i < v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]" << endl;
}

class Solution {
public:
   vector<int> findPermutation(string s) {
      stack<int> st;
      vector<int> ret;
      for(int i = 1; i <= s.size(); i++){
         if(s[i - 1] == 'D'){
            st.push(i);
         }
         else{
            ret.push_back(i);
            while(!st.empty()){
               ret.push_back(st.top());
               st.pop();
            }
         }
      }
      st.push(s.size() + 1);
      while(!st.empty()){
         ret.push_back(st.top());
         st.pop();
      }
      return ret;
   }
};

main(){
   Solution ob;
   print_vector(ob.findPermutation("DIID"));
}

실행 결과

입력

"DIID"

출력

[2, 1, 3, 5, 4]

동작 과정 살펴보기

입력 "DIID"에 대해 알고리즘이 어떻게 동작하는지 단계별로 확인해 보겠습니다.

i = 1: s[0]이 'D'이므로 1을 스택에 push합니다. (스택: [1])
i = 2: s[1]이 'I'이므로 2를 ret에 추가하고, 스택에서 1을 꺼내 ret에 추가합니다. (ret: [2, 1])
i = 3: s[2]가 'I'이므로 3을 ret에 추가합니다. (ret: [2, 1, 3])
i = 4: s[3]이 'D'이므로 4를 스택에 push합니다. (스택: [4])
반복 종료 후: 5(s.size() + 1)를 스택에 push한 뒤, 5와 4를 차례로 꺼내 ret에 추가합니다. (ret: [2, 1, 3, 5, 4])

복잡도 분석

각 숫자는 스택에 최대 한 번 push되고 한 번 pop되므로, 시간 복잡도는 O(n), 공간 복잡도 역시 O(n)입니다. 여기서 n은 입력 문자열의 길이입니다.