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

 

시간 제한 5초
N(1 <= N <= 10,000,000)
수는 10,000보다 작거나 같은 자연수

 

 

 

문제에서 주어진 입력 범위(최대 10,000,000개의 수)를 고려할 때

시간 복잡도가 O(N log N)인 Arrays.sort()는 제한된 시간 내에 완료되지 않을 가능성이 높다.

실제로 시간 초과핑;;;

 

 

 

이 문제는 숫자들이 10,000 이하의 자연수라는 조건을 이용해

계수 정렬(Counting Sort)을 사용하면 효율적으로 해결할 수 있다.

 

 

🔍 계수 정렬 _____ 시간 복잡도 O(N)

데이터의 크기 범위가 제한된 경우에 사용할 수 있는 정렬 알고리즘이다.
각 숫자의 빈도를 세는 배열을 만들어서 정렬하는 방식으로 매우 효율적이다.
이 문제처럼 최대값이 10,000 이하일 때 적합하다.


알고리즘 개요
1. 빈도 배열 생성
2. 빈도 배열 기록
3. 정렬 결과 생성

 

런타임 에러 뜬 코드 🐽

웃겨,,

 

런타임 에러가 뜬 이유는 count 배열의 크기를 잘못 설정했기 때문이다.

N은 1부터 10,000까지 포함될 수 있기 때문에 count[10000]에 접근할 수 있어야 한다.

따라서 배열의 크기를 10001로 설정하면 ArrayIndexOutOfBoundsException이 발생하지 않는다.

 

 

 

 

📖 정답 코드

import java.io.*;

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

        // 빈도 배열 생성
        int[] count = new int[10001];

        // 빈도 배열에 기록 (num이 3이면 count[3]++)
        for(int i=0; i<N; i++) {
            int num = Integer.parseInt(br.readLine());
            count[num]++;
        }

        StringBuilder sb = new StringBuilder();
        // 결과 출력
        for(int i=0; i<count.length; i++) {
            while(count[i] > 0) { // (count[3]이 2라면 2번 반복)
                sb.append(i+"\n");
                count[i]--;
            }
        }

        System.out.println(sb);
    }
}