[백준 2751번] 수 정렬하기 2(Java)

 

시간 제한 2초
N(1 <= N <= 1,000,000)
수는 절대값이 1,000,000보다 작거나 같은 정수

 

 

https://chaereemee.tistory.com/60

[백준 10989번] 수 정렬하기 3(Java)

 

 

전 포스팅을 보면 숫자의 범위가 최대 10,000까지여서 계수 정렬을 사용했는데

이 문제에서는 숫자 범위가 최대 1,000,000까지 있으므로, 계수 정렬을 사용하면 메모리 제한에 걸린다.

또한 배열의 크기를 1,000,001로 해야 하므로 비효율적이다.

Arrays.sort()는 입력 데이터가 너무 많거나 정렬에 최악의 경우가 발생할 때 시간 초과가 발생할 수 있다.

 

 

이 문제를 해결하기 위해

Merge Sort와 같은 안정적인 O(N log N) 정렬 방법을 사용하거나,

트리셋(TreeSet)을 활용한 정렬 방법을 사용할 수 있다.

Java의 TreeSet을 사용하면 중복을 허용하지 않고 정렬된 상태로 저장하므로

중복이 없는 입력에서는 효율적이다.

 

 

 

 

2751번 문제에서 수는 중복되지 않는다고 했으니까 TreeSet을 활용한 정렬 방법을 사용하자

 

🔍 TreeSet _______ 삽입 및 정렬의 시간 복잡도 O(log N)
TreeSet<Integer> sortedSet = new TreeSet<>();
➡️ 중복을 제거하면서 정렬된 상태로 숫자를 저장한다.
- add()로 숫자를 추가하면 TreeSet이 자동으로 정렬 유지한다.

 

 

 

 

📖  정답 코드

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());

        TreeSet<Integer> sortedSet = new TreeSet<>();
        for(int i=0; i<N; i++) {
            sortedSet.add(Integer.parseInt(br.readLine()));
        }

        StringBuilder sb = new StringBuilder();
        for(int num : sortedSet) {
            sb.append(num+"\n");
        }

        System.out.println(sb);
    }
}