문자 'D'와 'I'로 구성된 비밀 서명이 있다고 가정합니다. 'D'는 두 숫자 사이의 감소 관계를 나타내고 'I'는 두 숫자 사이의 증가 관계를 나타냅니다. 그리고 비밀 서명은 1에서 n까지의 다른 모든 숫자를 고유하게 포함하는 특수 정수 배열로 구성되었습니다.
예를 들어, 비밀 서명 "DI"는 [2,1,3] 또는 [3,1,2]와 같은 배열에서 구성될 수 있지만 [3,2,4] 또는 [2, 1,3,4], 둘 다 "DI" 비밀 서명을 나타낼 수 없는 특수 문자열을 구성하는 불법입니다.
이제 입력에서 주어진 비밀 서명을 참조할 수 있는 [1, 2, ... n]의 사전순으로 가장 작은 순열을 찾아야 합니다.
따라서 입력이 "DI"와 같으면 출력은 [2,1,3]이 됩니다. 알다시피 [3,1,2]도 비밀 서명 "DI"를 구성할 수 있지만 사전 순열이 가장 작은 경우 [2,1,3]
을 출력해야 합니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
하나의 스택 정의
-
cnt :=2
-
ret 배열 정의
-
initialize i :=1의 경우, i <=s의 크기일 때 업데이트(i를 1만큼 증가), 수행 -
-
s[i - 1]이 'D'와 같으면 -
-
i를 st에 삽입
-
-
그렇지 않으면
-
ret 끝에 i 삽입
-
동안(st가 비어 있지 않음) -
-
ret의 끝에 st의 최상위 요소 삽입
-
st
에서 요소 삭제
-
-
-
-
s의 크기를 st에 삽입
-
동안(st가 비어 있지 않음) -
-
ret의 끝에 st의 최상위 요소 삽입
-
st
에서 요소 삭제
-
-
리턴 렛
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#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;
int cnt = 2;
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, ]