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

문제

시간 복잡도가 O(nlogn)인 정렬 알고리즘으로 풀 수 있습니다. 예를 들면 병합 정렬, 힙 정렬 등이 있지만, 어려운 알고리즘이므로 지금은 언어에 내장된 정렬 함수를 쓰는 것을 추천드립니다.

2751번 - 수 정렬하기 2 문제 링크
입력된 숫자들을 오름차순 정렬시키는 문제(단, 시간복잡도가 O(nlogn)여야 함)

문제 설명

• 2750번 - 수 정렬하기 문제와 같은 문제지만 시간복잡도 제한이 늘었다.

• 2750번 문제를 풀 때 방식인 bubble sort나 Arrays.sort를 사용한다면 시간 초과가 뜨게 될 수 있다.

• **기본적으로 시간복잡도를 줄여야 하는 문제에서는 Scanner를 이용한 입출력보다는 Buffer를 이용한 입출력을 쓰는 것이 좋다.

• 시간복잡도 관련 참고글 - 각 언어별 input method 비교

  문제 풀이 방법

1. Priority Queue 사용

   • 우선순위 큐란? 일반적인 큐와 같은 FIFO가 아닌 키값의 크기에 의해 in, out이 결정되는 큐
   • heap아란? 우선순위 큐의 한 종류, 완전 이진트리, mqx heap, min heap
   • 참고 - 히프(heap)와 우선순위 큐(priority queue)

2. Merge Sort 사용

   • Merge Sort란? 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법
   • 분할 정복 알고리즘의 하나, 안정 정렬에 속함
   • 참고 - [알고리즘] 합병 정렬(merge sort)이란

3. Quick sort 사용

   • Quick Sort란? 하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법
   • 분할 정복 알고리즘의 하나, 매우 빠른 수행 속도
   • 참고 - [알고리즘] 퀵 정렬(quick sort)이란

4. TreeSet 사용

   • TreeSet이란? 이진검색트리 형태로 데이터를 저장하는 컬랙션 클래스
   • 중복을 허용하지 않기 때문에 중복이 있는 정렬에서는 사용할 수 없다.
   • 참고 - 자바 TreeSet

5. Collections.sort 사용

   • 입출력을 모두 Buffer로 해줌

성공 코드

1. Priority Queue, Quick sort, Merge Sort 사용

• 백준 #2751 / 수 정렬하기 2(우선순위 큐, Merge, Quick Sort) 참고

2. TreeSet 사용

   import java.io.BufferedReader;
   import java.io.BufferedWriter;
   import java.io.InputStreamReader;
   import java.io.OutputStreamWriter;
   import java.util.TreeSet;
   import java.io.IOException;
   
   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)));  
       StringBuilder sb = new StringBuilder();
   
           int N = Integer.parseInt(br.readLine());
           TreeSet<Integer> ts = new TreeSet<>();
   
           for (int i = 0; i < N; i++)
               ts.add(Integer.parseInt(br.readLine()));
   
           for (int i : ts)
               bw.write(i + "\n");
   
           br.close(); bw.close();
       }
   }

3. Collections.sort 사용 (입출력을 Buffered를 사용함)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.ArrayList; 
import java.util.Collections;

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());
        ArrayList<Integer> arr = new ArrayList<Integer>();

        for (int i = 0; i < n; i++) 
            arr.add(Integer.parseInt(br.readLine()));

        Collections.sort(arr);

        for (int i = 0; i < n; i++)
            bw.write(arr.get(i) + "\n");
        bw.flush(); bw.close();
    }
}