[백준][JAVA] 10989: 수 정렬하기3

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

10989번: 수 정렬하기 3

 

	시간제한	메모리제한	주어진 수의 개수
2750번 수 정렬하기	1초	128MB	1000개
2751번 수 정렬하기2	2초	256MB	1,000,000개
10989번 수 정렬하기3	3초	8MB	10,000,000개

표와 같이 2750번, 2751번 보다 10989번에서 주어지는 수의 개수가 훨씬 많다.

앞선 두 문제는 BufferedReader, Collections.sort(), StringBuilder를 사용한 동일한 코드로 통과가 가능했지만

10989번 문제에서는 8MB라는 빡빡한 메모리 제한이 있어 첫 시도에 시간 초과가 아닌 메모리초과가 발생했다.

 

2021.08.09 - [Algorithm] - [백준][JAVA] 2750: 수 정렬하기

[백준][JAVA] 2750: 수 정렬하기

 

2021.08.09 - [Algorithm] - [백준][JAVA] 2751: 수 정렬하기2

[백준][JAVA] 2751: 수 정렬하기2

 

방법은 sort 함수 대신 Counting Sort를 사용하는 것이다.

Array.sort 또는 Collection.sort 다 O(N^2)인 반면,

Counting Sort는 O(N+K)로 데이터가 많을수록 O(N)에 가까운 시간복잡도를 가져 비교적 매우 빠르다.

 

Counting Sort 참고 블로그 : https://st-lab.tistory.com/104

자바 [JAVA] - 카운팅 정렬 (Counting Sort / 계수 정렬)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N= Integer.parseInt(br.readLine());
        int[] count = new int[10001];
 
        for (int i = 0; i < N; i++) 
            count[Integer.parseInt(br.readLine())] ++;
         
        for(int i = 1; i < 10001; i++){
            while(count[i] > 0){
                sb.append(i).append('\n');
                count[i]--;
            }
        }
        System.out.println(sb);
        br.close();
    }
}