[백준/C++] 11656번_접미사 배열

이수진·2021년 12월 29일
0

문제는 다음과 같습니다.

저는 이 문제를 보고 우선 순위 큐 밖에 떠오르질 않았습니다.
문자열을 자른 후, 우선순위 큐에서 오름차순 정렬기능을 이용해야겠다! 라고 생각했고, 저의 코드는 다음과 같습니다.

#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;
}
profile
꾸준히, 열심히, 그리고 잘하자

0개의 댓글