PriorityQueue : 우선순위 큐(Java)

 

 

 

 

우선순위 큐(Priority Queue)

BOJ 11656 기본문제를 보다가 우선순위 큐를 적용해서 풀어보았다. 쉽게도 풀 수 있지만, 요즘에는 최대한 시간복잡도를 줄이면서 풀도록 노력하고 있다. N의 최댓값이 1000이고 O(N2)이라 시간초과가 나지 않을거 같긴한데 PriorityQueue로 O(N)으로 순서를 직접적으로 정렬하면서 진행한다면 훨씬 수월할 거라 판단. 구현을 시작했다. 

 

접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열이다.
baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekjoon, ekjoon, joon, kjoon, n, on, oon이 된다.
문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 다음 출력하는 프로그램을 작성하시오.

 

일단 우선순위 큐의 성질에 대해 알 필요가 있는데, 자료구조 안의 인스턴스에 중요도를 매기고 그에 따라 트리가 구성되는 형식이다. 때문에 queue에 offer할 때마다 미리 지정해둔 우선순위에 따라 정렬되기 때문에 반복문을 중첩으로 사용하지 않아도 된다.

 

ex 최소힙 트리

 

 

 

 

풀이




어렵지 않게 Queue를 사용하면 O(n)으로 해결 가능하다.

package com.company;
import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException
    {
        String input = br.readLine();
        
        //String에 사전순 정렬 Comp 우선도를 지정해준다.
        PriorityQueue<String> pq = new PriorityQueue<String>(Comp);
        int length = input.length();

        for(int i=0;i<length;i++)
        {
            String tmp= input.substring(i);
            pq.offer(tmp);
        }
        //flush!
        print(pq);     
    }
    private static Comparator<String>Comp = new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            // TODO Auto-generated method stub
            return o1.compareTo(o2);
        }
    };
    public static void print(PriorityQueue<String> pq) throws IOException
    {
        while(!pq.isEmpty())
        {
            bw.write(pq.poll()+"\n");
        }
        bw.flush();
    }
}