[C++] 백준 - 11656번 문제

11656번: 접미사 배열 (acmicpc.net)

11656번: 접미사 배열

 

11656번 : 접미사 배열

---

접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열이다.

baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, on, oon이 된다.

문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 다음 출력하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다.

 

 

출력

---

첫째 줄부터 S의 접미사를 사전순으로 한 줄에 하나씩 출력한다.

 

 

 

---

 

생각해 볼 점

---

정렬 문제입니다.

 

STL을 잘 활용하면 쉽게 풀 수 있습니다.

 

정렬은 Sort, 문자열은 String의 substr()을 활용하면 손쉽게 풀 수 있습니다.

 

코드

---

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
int main()
{
    //벡터 1칸 초기화 및 입력
    vector<string> arr_str(1);
    cin >> arr_str[0];

    //벡터 리사이즈
    int N = arr_str[0].length();
    arr_str.resize(N);

    //이전 칸에선 앞 한글자만 자르고 다음 칸에 저장
    for(int i = 1; i < N; i++)
        arr_str[i] = arr_str[i - 1].substr(1);

    //정렬
    sort(arr_str.begin(), arr_str.end());

    //출력
    for(string str : arr_str)
        printf("%s\n", str.c_str());
    return 0;
}

 

그 외

---