K번째 문자열

문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18KWf6ItECFAZN&categoryId=AV18KWf6ItECFAZN&categoryType=CODE4

SW Expert Academy

 

알고리즘

 

1. 반복문을 이용하여 substr을 구하고 우선순위 큐에 넣는다.

 

2. 큐에서 주어진 index를 빼며 답을 구한다.

 

주의사항

 

1. 우선순위 큐에 substr을 담았기 때문에 중복제거는 반복문 1개로 가능하다.

 

2. 우선순위 큐를 이용하여 정렬할 때 문제에 주어진 조건을 잘 읽어봐야 한다.

-> 길이에 상관없이 앞부분이 사전적 정렬이 되어야 한다.

 

구현

class substr implements Comparable<substr>{
    String st;

    @Override
    public int compareTo(substr o) {
        if(this.st.length() >= o.st.length()) // 길이가 같거나 크면
        {
            for (int j = 0; j < o.st.length(); j++) {
                if(this.st.charAt(j) > o.st.charAt(j))
                    return 1;
                if(this.st.charAt(j) < o.st.charAt(j))
                    return -1;        
            }
        }
        else if(this.st.length() < o.st.length())
        {
            for (int j = 0; j < this.st.length(); j++) {
                if(this.st.charAt(j) > o.st.charAt(j))
                    return 1;
                if(this.st.charAt(j) < o.st.charAt(j))
                    return -1;        
            }
        }
        return this.st.length() - o.st.length();
    }

    public substr(String st) {
        super();
        this.st = st;
    }

}
class Solution_K번째문자열
{
    static int N;

    public static void main(String args[]) throws Exception
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine().trim());
        for (int test_case = 1; test_case <= T; test_case++) 
        {
            int a_index = Integer.parseInt(in.readLine().trim());
            String q = in.readLine();
            PriorityQueue<substr> pq = new PriorityQueue<substr>();
            ///////////////////substr 구하는 과정////////////////////////
            for (int size = 1; size <= q.length(); size++) {
                int a=0;
                for (int i = q.length()-size; i >-1; i--) {
                    pq.offer(new substr(q.substring(a,a+size)));
                    a++;
                }
            }

            substr word;
            String temp = pq.peek().st;
            a_index--;
            while(!pq.isEmpty() && a_index != 1){
                word = pq.poll();
                if(!temp.equals(word.st)) //temp와 st가 다르면 count -> 중복제거
                {    a_index--;
                    temp = word.st;
                }
            }
            System.out.print("#"+test_case+" ");
            System.out.println(a_index == 1 ? pq.poll().st:-1);
        }//end TK
    }    
}