백준 10989: 수 정렬하기 3과 카운팅 정렬

백준 10989번 수 정렬하기 3은 시간과 메모리 제한을 함께 고려해야 하는 문제였습니다. 입력값의 범위가 1부터 10,000까지라는 점을 이용해 카운팅 정렬로 풀었습니다.

값을 저장하는 대신 횟수를 셉니다

크기가 10,000인 배열을 만들고 입력값에서 1을 뺀 위치의 횟수를 늘립니다. 입력이 끝나면 배열의 앞에서부터 순회하며 각 값을 등장한 횟수만큼 출력합니다. 배열 인덱스는 0부터 시작하므로 출력할 때는 다시 1을 더합니다.

카운트 배열의 크기는 고정되어 있지만 이 코드는 출력 전체를 StringBuilder에 모읍니다. 그래서 전체 메모리 사용량까지 고정 크기라고 볼 수는 없습니다.

입력을 마친 뒤에는 br.close()로 자원을 닫았습니다. 당시 주석에서는 이를 가비지 컬렉터와 연결했지만, BufferedReader.close()는 스트림을 닫고 연결된 시스템 자원을 해제하는 메서드입니다. 이 호출은 가비지 컬렉션을 실행하지 않으며 프로그램 전체의 메모리 사용량 문제를 해결해 주지도 않습니다.

Java

import java.io.*;

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

        // 0~9999 의 범위 따라서 출력할 때 1을 더해서 출력
        int[] arr = new int[10000];
        for (int i = 0; i < N; i++) {
            arr[Integer.parseInt(br.readLine())-1]++;
        }
        //입력 끝나면 닫아주기, Garbage Collector를 너무 의존하지 말자
        br.close();

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < 10000; i++) {
            while (arr[i] > 0) {
                sb.append(i+1).append("\n");
                arr[i]--;
            }
        }
        bw.write(sb.toString());
        bw.flush();
    }
}