[BaekJoon-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의 접미사를 사전순으로 한 줄에 하나씩 출력한다.

예제 입력 1

baekjoon

예제 출력 1

aekjoon
baekjoon
ekjoon
joon
kjoon
n
on
oon

시작 위치마다 접미사 만들기

접미사는 문자열의 어떤 위치에서 시작해 끝까지 읽은 결과다. 길이 n의 문자열에는 시작 위치가 0부터 n-1까지이므로 접미사도 정확히 n개다. baekjoon에서 위치 0은 baekjoon, 위치 1은 aekjoon, 마지막 위치는 n이 된다. 빈 문자열은 접미사로 출력하지 않는다.

코드는 각 위치에 substring(i)를 적용해 배열에 넣고 Arrays.sort로 사전순 정렬한다. 원본 문자열을 그대로 출력하면 시작 위치 순서이지 사전순이 아니다. 이 예에서는 joon이 kjoon보다 앞서고, on은 oon보다 앞선다. 접미사 길이가 서로 다를 때 한쪽이 다른 쪽의 접두사이면 짧은 쪽이 먼저 오는 규칙도 문자열 비교에 포함된다.

접미사의 총 문자 수는 n+(n-1)+…+1이므로 문자열을 실제로 복사하는 이 구현의 공간은 O(n²)이다. 정렬은 O(n log n)번 비교하지만 한 번의 비교에 최대 O(n) 문자가 필요해 상한은 O(n² log n)이다. n≤1,000에서는 간단한 풀이가 충분하다. 문자열 aaa처럼 같은 글자가 반복되어도 a, aa, aaa를 각각 출력해야 한다.

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) throws Exception {
        suffixOfArray();
    }

    public static void suffixOfArray() throws Exception {
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String str = in.readLine();
        String[] arr = new String[str.length()];

        for (int i = 0; i<str.length(); i++) {
            arr[i] = str.substring(i);
        }
        Arrays.sort(arr);
        for (String s : arr) {
            out.write(s+'\n');
        }
        out.flush();
        out.close();;
        in.close();
    }
}