백준 10989. 수 정렬하기 3(카운팅 정렬)

 

문제

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

 

입력

 

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

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

정답

카운팅 정렬을 이용해야 한다. 카운팅 정렬은 비교 기반 정렬이 아니라 빈도수를 기반으로 데이터를 정렬하는 알고리즘이다. 데이터 값의 크기를 직접 비교하지 않고 각 값의 등장 횟수를 기반으로 데이터의 정렬 위치를 결정한다.

 

로직 단계별 설명

1. 데이터 범위 확인
   • 주어진 데이터의 최소값과 최대값을 찾습니다.
   • 이를 통해 값의 범위 크기를 결정하고, 해당 범위를 저장할 배열(count)을 준비합니다.
2. 카운트 배열 생성
   • 원래 배열의 각 요소가 몇 번 등장하는지 계산하여 count 배열에 저장합니다.
   • count[i]는 원래 배열에서 값 i가 등장한 횟수를 나타냅니다.
3. 누적합 계산
   • count 배열에서 누적합을 계산합니다.
   • count[i]는 값 i가 정렬된 배열에서 마지막으로 위치할 인덱스를 의미합니다.
   • 이 단계는 데이터를 정렬된 배열에 올바르게 배치하기 위해 필요합니다.
4. 정렬된 배열 생성
   • 원래 배열을 역순으로 순회하면서 정렬된 배열의 올바른 위치에 데이터를 삽입합니다.
   • 삽입한 후에는 count 값을 1 감소시켜 다음 같은 값의 위치를 조정합니다.
   • 역순으로 순회하는 이유는 정렬이 안정적이도록 하기 위함입니다(같은 값의 상대 순서 유지).
5. 결과 반환
   • 최종적으로 정렬된 배열을 반환합니다.

package test;

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

public class test55 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		try {
			int n = Integer.parseInt(br.readLine());
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = Integer.parseInt(br.readLine());
			}
			int max = Arrays.stream(arr).max().getAsInt();
			int min = Arrays.stream(arr).min().getAsInt();
			int range = max - min + 1;
			// 카운팅 배열 생성, 초기화
			int[] cnt = new int[range];
			int[] output = new int[arr.length];
			// 등장 횟수 기록
			for (int i = 0; i < arr.length; i++) {
				cnt[arr[i] - min]++;
			}
			// 누적합 계산
			for (int i = 1; i < cnt.length; i++) {
				cnt[i] += cnt[i - 1];
			}
			// 정렬 수행
			for (int i = arr.length - 1; i >= 0; i--) {
				output[cnt[arr[i] - min] - 1] = arr[i];
				cnt[arr[i] - min]--;
			}
			for(int item:output) {
				bw.write(String.valueOf(item));
				bw.write("\n");
			}
			bw.flush();
		} catch (NumberFormatException | IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

	}

}