[BOJ] 백준 10989번 : 수 정렬하기 3 (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

 

비슷한 문제

-2750번 수 정렬하기 문제

-2751번 수 정렬하기 2 문제

 

풀이

수 정렬하기, 수 정렬하기 2와 N의 범위를 제외하면 완전히 동일한 문제였습니다.

하지만, 이번에는 Arrays.sort와 Collection.sort 전부 통하지 않았고, 메모리 제한때문에 천만 개의 데이터를 저장할 수도 없었습니다.

구글에 검색을 해 본 결과, 카운팅 소트라는 기법을 이용해야했습니다. 이 카운팅 소트 관련해서는 아래 블로그를 참조하시면 되겠습니다.

https://yaboong.github.io/algorithms/2018/03/20/counting-sort/

Counting Sort - 계수정렬

간략하게 말하자면, 정렬하고자 하는 요소의 개수를 센 다음 누적합을 이용해서 정렬을 하는 것이었습니다.

하지만, 이 문제는 위와 같은 정통적인 카운팅 소트도 먹히질 않았습니다. 이유는 위에서 언급한 메모리 문제때문이었죠.

따라서 필연적으로 최적화를 해야합니다.

문제에서 최댓값은 10000이라고 했기때문에 count 배열의 개수를 10001로 지정해 놓고, N(최대 10^7)개의 데이터에 대하여 각각의 개수를 count 배열에 저장합니다. 

그리고, count 배열에서 존재하는 요소의 수 만큼 인덱스를 출력해 주면 됩니다.

 

아래는 위 로직을 작성한 소스코드입니다.

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int N = Integer.parseInt(br.readLine());
        int[] count = new int[10001];
        
        // 각 원소의 개수를 저장한다.
        for (int i = 0; i < N; i++) {
            int input = Integer.parseInt(br.readLine());
            count[input]++;
 
        }
        
        StringBuilder sb = new StringBuilder();
        
        // 존재하는 원소의 수만큼 i를 출력한다.
        for (int i = 1; i <= 10000; i++) {
            for (int j = 0; j < count[i]; j++) {
                sb.append(i + "\n");
            }
        }
 
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}
 

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.