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

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

11656번: 접미사 배열

 

방법 1: 접미사 배열을 만든 후, 접미사들을 배열

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    // 입력
    string input;
    cin >> input;
    int len = input.size();
 
    // 벡터에 부분문자열 집어넣기
    vector<string> suffix(len);
    for (int i = 0; i < len; i++)
    {
        suffix[i] = (input.substr(i, len));
    }
 
    // 오름차순 정렬
    sort(suffix.begin(), suffix.end());
 
    // 출력
    for (string s : suffix)
    {
        cout << s << endl;
    }
 
    return 0;
}

 

방법 2: 문자열을 출력시킬 인덱스값만 정렬. 접미사 배열을 따로 만들지 않음. 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    // 입력
    string input;
    cin >> input;
    int len = input.size();
 
    /*
        들어온 문자열은 그대로 있고, 
        문자열을 출력시킬 인덱스 값만 정렬하는 방법
    */
 
    // 벡터에 각 0 < idx < len  인덱스 값 집어넣기
    vector<int> str_idx(len);
    for (int i = 0; i < len; i++)
    {
        str_idx[i] = i;
    }
 
    /*
        람다함수로 새로운 정렬기준 설정
 
        문자열을 가리키는 포인터를 사용해서
        u 번째부터 시작되는 문자열과
        v 번째부터 시작되는 문자열을 비교.
        비교 결과를 오름차순으로 벡터 정렬
    */
    sort(str_idx.begin(), str_idx.end()
        , [&input](int u, int v) 
        {
            return strcmp(input.c_str() + u, input.c_str() + v) < 0;
        }
    );
    
    /*
        정렬된 벡터의 요소값에 해당하는 인덱스부터 문자열 출력.
 
        ex) 벡터가 1 5 2 4 3 으로 정렬되었다고 하면,
        문자열은 1번째 문자부터, 5번째 문자부터, 2번째 문자부터의 순으로 출력된다.
    */
    for (int &i : str_idx)
    {
        cout << input.substr(i) << '\n';
    }
 
    return 0;
}

 

TIP1

방법 2가 매우 굳굳이다!

내가 생각한 것은 아니고, 코드플러스 교재를 많이 참고하였다 ㅜㅜ

 

접미사 배열을 만들고 걔네를 또 정리하고 할 필요가 없다.

출력을 시작할 인덱스를 담은 벡터만 정렬해주면 된다.

비교방법 : (input을 가리키는 포인터 + 인덱스) 를 비교하기

 

작년에 같은 문제를 java로 풀이했던 방식을 생각하면 눈물이 앞을 가리는데...ㅋㅋㅋㅋㅋ

장족의 발전이다. 

확실히 포인터를 알고 모르고의 차이가 크구나

 

 

TIP2

내림차순 정렬 : 람다 함수의 리턴값을 (식 > 0) 으로

[&input](int u, int v) {
    return strcmp(input.c_str() + u, input.c_str() + v) > 0;
}