[BOJ] 11656 접미사 배열 c++ (priority_queue)

 

https://www.acmicpc.net/problem/11656

 

✔ 문제이해

한 단어의 모든 접미사를 알파벳 순서대로 정렬하라

 

✔ 풀이 + 코드

다른사람들 다 풀듯이 문자열 자르고 vector에 저장해서 정렬하는 방식을 사용했는데 시간이 오래걸려서 백준에 있는 다른 사람의 풀이를 참조했다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    string s = "";
    vector<string> str;

    cin >> s;

    for(int i = 0; i < s.size(); ++i)
    {
        str.push_back(s.substr(i, s.size()));
    }
    sort(str.begin(), str.end());

    for(int i = 0; i < str.size(); ++i)
    {
        cout << str[i] << "\n";
    }
    return 0;
}

 

우선순위 큐로 풀었는데 완전 이진트리로 구성된 우선순위 큐의 속도이다. 정렬된 배열에서 꺼내는 속도가 엄청 빠르다. 앞으로 나도 정렬된 배열이나 리스트에서 뺄 때 우선순위큐를 사용해야겠다.

그런데 메모리가 좀 많이 소모된다는 것을 잊지말자..!

출처 : https://suyeon96.tistory.com/31

 

#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>

using namespace std;

int main(){
    string S;
    priority_queue<string,vector<string>,greater<string>> Ss;
    cin>>S;
    for(int s=0;s<S.size();s++){
        Ss.push(S.substr(s));
    }
    S="";
    while(Ss.size()){
        S+=Ss.top()+'\n';Ss.pop();
    }
    cout<<S;
    return 0;
}

 

✔ 피드백

정렬된 배열을 top으로 꺼내면서 사용할 때 우선순위큐를 쓰자! 

 

✔ reference

https://www.acmicpc.net/source/26381624