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

[작성일: 2023. 10. 16]

 

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

 

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.valueOf(br.readLine());
        }
        Arrays.sort(nums);
        for (int num : nums) {
            System.out.println(num);
        }
        br.close();
    }
}

 

이 문제는 Arrays.sort로도 시간/메모리 초과가 나지 않아서 문제를 쉽게 풀 수 있었다.

그런데 공부하다가 보니 계수정렬(=카운팅정렬)이라는 것을 알게 되어 코드에 적용해보았다.

 

카운팅정렬은 입력 값의 범위가 제한적일 때 효율적으로 사용할 수 있는데, 이 문제는 10,000보다 작거나 같은 자연수라고 범위가 정해져있기 때문에 카운티정렬을 적용할 수 있었다.

 

1. 입력 데이터의 범위를 확인한다. 입력 데이터가 0~10,000 사이이므로 크기가 10,001인 카운팅 배열을 만든다.
2. 입력 데이터를 순회하며 해당 정수의 카운트를 증가시킨다. 입력 데이터에 5가 세 번 등장한다면 카운팅 배열의 5번 인덱스 값은 3이 된다.
3. 카운팅 배열을 순서대로 순회하며 정렬된 결과를 출력한다. 카운팅 배열의 5번 인덱스 값이 3이면 5를 세 번 출력한다.

 

카운팅정렬은 시간복잡도가 O(n+k)이다. 여기서 n은 원수의 개수, k는 입력데이터의 최댓값이 된다. 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

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.valueOf(br.readLine());
        int[] counting = new int[10001];
        for (int i = 0; i < n; i++) {
            counting[Integer.valueOf(br.readLine())]++;
        }
        for (int j = 1; j <= 10000; j++) {
            while (counting[j] > 0) {
                bw.write(j + "\n");
                counting[j]--;
            }
        }
        br.close();
        bw.flush();
        bw.close();
    }
}

 

처음 입력을 받을 때 counting 배열의 인덱스로 사용해서 해당 인덱스의 값을 1 증가시킨다.

입력받은 숫자가 5라면 counting[5] 값을 1 증가시킨다. (5가 2번 나왔으면 counting[5]는 2가 되어있을 것이다.)

 

counting[i]는 i가 몇 번 나타났는지를 저장한 값이 된다.

while(count[i] > 0)은 i가 등장한 횟수만큼 해당 값을 출력하기 위한 반복문이 된다.

 

예를 들어 counting[5]의 값이 3이라면 숫자 5는 입력 데이터에서 3번 등장한 것이다. 그래서 5를 3번 출력한다.

i를 출력하고 나서 counting[i]--;는 i를 한 번 출력했으므로 i의 등장 횟수를 1 감소시킨다. count[i]의 값이 0이 될 때까지 반복하므로 각 숫자는 정확히 해당 숫자가 등장한 횟수만큼 출력하게 된다.