[Java] Boj 10867: 중복 빼고 정렬하기

문제

N개의 정수가 주어진다. 이때, N개의 정수를 오름차순으로 정렬하는 프로그램을 작성하시오. 같은 정수는 한 번만 출력한다.

입력

첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 수를 오름차순으로 정렬한 결과를 출력한다. 이때, 같은 수는 한 번만 출력한다.

---

풀이

태그에는 정렬로 되어있지만 우선순위 큐를 이용해 해결한 문제.

작은 수부터 우선적으로 poll하는 우선순위 큐의 특성을 이용해 입력받은 수가 우선순위 큐에 존재하지 않는 경우에만 그 수를 큐에 add하고, 우선순위 큐가 빌 때까지 출력하여 문제 해결.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(bf.readLine());
        st = new StringTokenizer(bf.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i=0; i<n; i++) {
            int x = Integer.parseInt(st.nextToken());
            if (! pq.contains(x)) {
                pq.add(x);
            }
        }
        while (! pq.isEmpty()) {
            System.out.print(pq.poll() + " ");
        }
 
    }
}