문제는 다음과 같습니다.
저는 이 문제를 보고 우선 순위 큐 밖에 떠오르질 않았습니다.
문자열을 자른 후, 우선순위 큐에서 오름차순 정렬기능을 이용해야겠다! 라고 생각했고, 저의 코드는 다음과 같습니다.
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
priority_queue<string, vector<string>, greater<string> > pq;
string s;
cin>>s;
int size = s.size();
for(int i=0; i<s.size(); i++){
pq.push(s.substr(i, size-i));
}
while(!pq.empty()){
cout<<pq.top()<<"\n";
pq.pop();
}
return 0;
}
찾아보았더니, 또 다른 풀이가 있어 공유합니다.
바로 벡터의 정렬 기능을 이용하는건데요,
벡터에 각각의 접미사 문자열들을 넣은 후, 벡터의 sort 기능을 이용하는 것입니다.
코드는 다음과 같습니다.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin>>s;
vector<string> v;
int size = s.size();
for(int i=0; i<s.size(); i++){
v.push_back(s.substr(i, size));
}
sort(v.begin(), v.end());
for(int i=0; i<v.size(); i++) cout<<v[i]<<endl;
return 0;
}