백준 11656번: 접미사 배열 - C++

문제

접미사 배열은 문자열 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의 접미사를 사전순으로 한 줄에 하나씩 출력한다.

예시

입력	출력
baekjoon	aekjoon baekjoon ekjoon joon kjoon n on oon

제출한 답

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

int main() {
    string word;
    int len;
    
    cin >> word;
    len = word.length();
    string arr[len] = {};
    
    for (int i = 0; i < len; i++) {
        arr[i] = word.substr(i, len);
    }
    
    sort(arr, arr + len);
    
    for (int i = 0; i < len; i++) {
        cout << arr[i] << '\n';
    }
    
    return 0;
}

문자열 자르기 substr

word.substr(i, len)이란 word의 인덱스 i부터 len 전까지 문자열을 자르는 것이다.

반복문과 substr을 사용하여 모든 접미사를 arr에 입력한다.

오름차순 정렬 sort
sort(arr, arr + len)은 배열의 시작점 주소인 arr에서 마지막 주소인 arr + len까지 오름차순으로 재정렬 시키는 것이다.

주의할 점은 #include <algorithm>을 꼭 포함해야한다.

정렬을 마치면 반복문을 사용해 출력한다.