[SWEA] 1257. K번째 문자열

문제

1257. [S/W 문제해결 응용] 6일차 - K번째 문자열
주어진 문자열의 부분문자열을 사전순서대로 정렬한 다음, K번째 문자열을 출력. (없으면 none)

풀이

• Suffix Array 와 LCP를 이용해서 정리했다. (그냥 이걸 구현했다.)
• 한 문자열에서 여러번 K번째의 문자열을 찾는 게 아니라서, 누적개수가 K개를 넘어서면 바로 끊었다.

자바코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;

import java.io.FileInputStream;


class Solution
{
	static int size;
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T;
		T=sc.nextInt();
		int K;
		String str;
		String [] SA; // Suffix Array 
		int [] LCP; // 접두어가 이전과 다르기 시작하는 index 
		for(int test_case = 1; test_case <= T; test_case++)
		{
			K = sc.nextInt();
			str = sc.next();
			size = str.length();
			SA = new String[size];
			LCP = new int[size];

			makeSA(SA, str);
			String result = makeLCP(LCP, SA, K);
			
			if (result.equals("")) {
				System.out.println("#"+test_case +" none");
			} else {
				System.out.println("#"+test_case +" " + result);
			}
			
		}
	}
	
	public static void makeSA(String [] SA, String str) {
		for (int i=0; i<size; i++) {
			SA[i] = str.substring(i, size);
		}
		Arrays.sort(SA); // 정렬 
	}
	
	public static String makeLCP(int [] LCP, String [] SA, int K) {
		int cnt = 0; // 누적개수 

		LCP[0] = 0;
		for (int i=0; i<size; i++) {
			if (i>0) {
				int length = Math.min(SA[i].length(), SA[i-1].length());
				for (int j=0; j<length; j++) {
					if (SA[i].charAt(j) == SA[i-1].charAt(j)) {
						LCP[i]++;
					} else {
						break;
					}
				}
			}
			cnt += SA[i].length() - LCP[i]; // 현재까지 정렬된 개수
			if (cnt >= K) {
				int end = SA[i].length()-(cnt-K);
				return SA[i].substring(0, end);
			}
		}
		return ""; // K번째 문자열이 존재하지 않는다.
	}
}