BOJ 11656 - 접미사 배열

문제

BOJ 11656 - 접미사 배열

문자열 S가 주어졌을 때, S의 모든 접미사(suffix)를 사전순으로 정렬하여 출력하는 문제다. 접미사란 문자열의 특정 위치 i부터 끝까지 잘라낸 부분 문자열이다.

입력

• 첫째 줄: 문자열 S (길이 1 이상 1,000 이하, 알파벳 소문자로만 구성)

출력

S의 모든 접미사를 사전순으로 정렬하여 한 줄에 하나씩 출력한다.

예제

풀이

문자열의 각 인덱스에서 시작하는 접미사를 추출한 뒤 Arrays.sort로 사전순 정렬하여 출력한다.

1. 입력 문자열 S의 길이 N을 구한다.
2. 인덱스 0부터 N-1까지 substring(i, N)으로 접미사 N개를 배열에 저장한다.
3. Arrays.sort로 문자열 배열을 사전순 정렬한다.
4. 정렬된 접미사를 순서대로 출력한다.

핵심 아이디어: Java의 String.compareTo는 사전순 비교를 기본 제공하므로 Arrays.sort만으로 접미사 배열을 구성할 수 있다. 문자열 길이가 최대 1,000이므로 O(N^2 log N) 문자 비교가 발생해도 시간 제한 내에 충분히 통과한다.

코드

package com.ssafy.an.day049;
 
import java.util.Arrays;
import java.util.Scanner;
 
public class Day22BOJ11656접미사배열 { // 11656 접미사 배열
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
		int N = str.length();
		String[] ans = new String[N];
		for (int i = 0; i < N; i++) {
			ans[i] = str.substring(i, N);
		}
		Arrays.sort(ans);
		// 1문자가 같거나, 길이가 다른 글자 끼리 비교가 어려움
		for (int i = 0; i < N; i++) {
			System.out.println(ans[i]);
		}
		sc.close();
	}
}

복잡도

• 시간: O(N^2 log N) — 접미사 정렬 시 문자열 비교가 최대 N번 발생하므로
• 공간: O(N^2) — 접미사 문자열 N개를 배열에 저장