【C++】'D'と'I'の署名から辞書順最小の順列を見つけるアルゴリズム

問題概要

'D' と 'I' の2種類の文字だけで構成された「秘密の署名」を考えます。'D' は隣接する2つの数の間の減少関係を、'I' は増加関係を表します。この署名は、1 から n までの相異なる整数をすべて含む特別な整数配列から構成されます。

たとえば、署名 "DI" は [2, 1, 3] や [3, 1, 2] のような配列から構成できます。一方、[3, 2, 4] や [2, 1, 3, 4] のような配列では構成できず、不正な構成となります。

ここでの課題は、入力として与えられた署名に一致する [1, 2, ..., n] の順列のうち、辞書順で最小のものを見つけることです。

入力が "DI" の場合、出力は [2, 1, 3] になります。[3, 1, 2] も同じく "DI" を構成できますが、辞書順最小の順列を求める必要があるため、[2, 1, 3] が正解となります。

解法のアプローチ

この問題は、スタックを使った貪欲法で効率的に解けます。ポイントは次のとおりです。

• 'D' が出たら、その位置の番号をいったんスタックに積んで保留にします。こうすることで、後でスタックから取り出す際に降順（減少）になります。
• 'I' が出たら、現在の番号を出力配列に追加し、スタックに残っている番号をすべて取り出して出力配列の末尾に追加します。
• 最後に n + 1（n は署名の長さ）をスタックに積み、残りをすべて取り出します。

アルゴリズムの手順

1. スタック st と結果格納用の配列 ret を定義します。
2. i = 1 から s の長さまで繰り返します。
   • s[i - 1] が 'D' の場合：i を st にプッシュします。
   • それ以外の場合：i を ret の末尾に追加し、st が空になるまで st のトップ要素を ret の末尾へポップしていきます。
3. ループ終了後、s.size() + 1 を st にプッシュします。
4. st が空になるまで、トップ要素を ret の末尾へポップしていきます。
5. 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 をスタックにプッシュ → st = [1]
• i = 2：s[1] = 'I' なので、2 を ret に追加し、スタックから 1 を取り出して追加 → ret = [2, 1]
• i = 3：s[2] = 'I' なので、3 を ret に追加（スタックは空）→ ret = [2, 1, 3]
• i = 4：s[3] = 'D' なので、4 をスタックにプッシュ → st = [4]
• ループ後：5 をスタックにプッシュし、4、5 の順に取り出して追加 → ret = [2, 1, 3, 5, 4]

計算量

各要素は最大でも1回スタックにプッシュされ、1回ポップされるだけなので、時間計算量・空間計算量ともに O(n) で非常に効率的です。