백준 JAVA11 10989번 : 수 정렬하기 3

Mention : 계수 정렬(counting sort) + 기수 정렬(radix sort)

수 정렬하기 3

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
5 초 (https://www.acmicpc.net/problem/10989#)	8 MB (https://www.acmicpc.net/problem/10989#)	207659	48225	36482	23.504%

문제

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

입력

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

출력

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

예제 입력 1

10
5
2
3
1
4
2
3
5
1
7

예제 출력 1

1
1
2
2
3
3
4
5
5
7

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: cgiosy
• 문제의 오타를 찾은 사람: joonas

슈도 코드

N(정렬할 수 개수)
A(정렬할 배열 선언하기)
for(N만큼) {
	정렬할 배열 저장
}
기수정렬 함수 실행
최종 정렬된 Bucket 출력

기수정렬 함수 구현부
Bucket(각 자릿수의 분포 합배열)
Bucket[10] 현재 기준 자릿값이 0~9까지 몇개의 데이터가 있는지 저장
output(임시 정렬을 위한 배열)
digit(현재 자릿수)
while(최대자릿수만큼) {
	현재 기준 자릿수를 기준으로 A 배열 데이터를 Bucket에 카운트
	합 배열 공식으로 Bucket을 합 배열형태로 변경 (카운트정렬)
	for(i가 N-1에서 0까지 감소하면서 반복문) {
		Bucket값을 이용해 현재 기준 자릿수로 데이터를 정렬
		(카운트정렬)
		output 배열에 저장
	}
	for(N의 개수) {
		다음 자릿수 이동을 위해 A배열에 output데이터 저장
	}
	digit = digit * 10;
}

Code

package sort;

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

public class P10989_radixSort {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		int[] A = new int[N];

		for (int i = 0; i < N; i++) {
			A[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		
		PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();
		for(int i = 0; i < N; i++) {
			priorityQueueLowest.add(A[i]);
		}
		
		
		for(int i = 0; i < N; i++) {
			bw.write(priorityQueueLowest.poll() + "\n");
		}
		bw.flush();
		bw.close();
	}
}

Refactoring Code

package sort;

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

public class P10989_radixSort {
	public static int[] Bucket;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		int[] A = new int[N];

		for (int i = 0; i < N; i++) {
			A[i] = Integer.parseInt(br.readLine());
		}
		br.close();

		radixSort(A, 5);

		for (int i = 0; i < N; i++) {
			bw.write(A[i] + "\n");
		}
		bw.flush();
		bw.close();
	}

	private static void radixSort(int[] A, int maxDigit) {
		int[] output = new int[A.length];
		int digit = 1;
		int digitCnt = 0;

		while (digitCnt != maxDigit) {
			int[] bucket = new int[10];
			for (int i = 0; i < A.length; i++) {
				bucket[(A[i] / digit) % 10]++;
			}
			for (int i = 1; i < 10; i++) {
				bucket[i] = bucket[i - 1] + bucket[i];
			}
			for (int i = A.length - 1; i >= 0; i--) {
				output[bucket[(A[i] / digit % 10)] - 1] = A[i];
				bucket[(A[i] / digit) % 10]--;
			}
			for(int i = 0; i < A.length; i++) {
				A[i] = output[i];
			}
			digit = digit * 10;
			digitCnt++;
		}
	}

}