[BOJ] 백준 2751번 : 수 정렬하기 2 - Java

https://www.acmicpc.net/problem/2751

 

• PriorityQueue를 이용한 정렬

import java.io.*;
import java.util.*;

public class Main {
        public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine()); // 수의 개수
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        // 수의 개수만큼 반복문을 돌며 정렬할 숫자 저장
        for (int i=0; i<N; i++) {
            pq.add(Integer.parseInt(br.readLine()));
        } 

        // PriorityQueue : 우선순위 큐
        // 우선순위가 높은 데이터가 먼저 나가는(poll()) 자료 구조
        // 최소 힙을 사용하게 하여 오름차순으로 출력.

        // 출력
        for (int i=0; i<N; i++) {
            bw.write(pq.poll()+"\n");
        }
        bw.close();
    }
}

---

• 시간 초과

• ArrayList를 이용한 sort() 함수 사용
  • ArrayLis의 sort()는 dual-pivot Quicksort 알고리즘
  • 해당 알고리즘은 평균 시간복잡도 O(nlogn)이고, 최악의 경우 O(n^2)
  • 문제 조건이 1 ≤ N ≤ 1,000,000 이기 때문에, O(n^2)인 경우 2초를 초과하게 된다.
  • 시간 복잡도 참고

import java.io.*;
import java.util.*;

public class Main {
        public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 수의 개수
        
        List<Integer> list = new ArrayList<>(); // 정렬할 수들을 저장하기 위해 리스트 선언
        // 수의 개수만큼 반복문을 돌며 리스트에 숫자 저장
        for (int i=0; i<N; i++) {
            list.add(Integer.parseInt(br.readLine()));
        } 

        // ArrayList 오름차순 정렬
        list.sort(Comparator.naturalOrder());

        // 정렬된 list 출력
        for (int i=0; i<N; i++) {
            System.out.println(list.get(i));
        }
    }
}