[백준] 11656번 - 접미사 배열

 

 

단순하게 substring을 이용하여 각각의 string을 list에 저장하고, Collections의 sort 기능을 이용하여서 정렬한 값을 출력해주었다. Arrays.sort의 경우 퀵소트기반으로 worst case의 경우 시간복잡도가 O(N^2)이 되지만 Collections.sort는 머지소트 기반이므로 worst case 여도 O(NlogN)이 걸린다.

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class p11656 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);

		String s = sc.next();

		ArrayList<String> list = new ArrayList<>();

		for (int i = 0; i < s.length(); i++) {
			list.add(s.substring(i));
		}
		
		Collections.sort(list);
		
		for(String i : list) {
			System.out.println(i);
		}
	}
}