[백준] 1427 - 소트인사이드 (자바/Java) : 계수 정렬(Counting Sort)

문제

배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자.

입력

첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다.

---

자리수를 내림차순으로 정렬한다고 해서 계수 정렬(Counting Sort)가 생각 났다

계수 정렬은 O(N)의 시간 복잡도를 가지는 매우 빠른 정렬으로, 입력되는 숫자들의 범위가 작을수록 사용하기 좋다. 이 문제는 각 자리수를 정렬하는 것이니 0~9까지만 정렬하면 되기 때문에, 계수 정렬을 사용하여 빠른 정렬이 가능하다.

숫자를 String으로 입력 받아, charAt(i)를 이용하여 각 자리수를 int로 바꾸어 주었다.

그리고 0~9까지의 index를 가지는 count 배열의 값은, 그 index 값의 수와 같다.

즉 입력된 값에 0이 10개가 있다면, count[0]의 값이 10인 것이다.

이를 출력하기 위해 이중 for문을 돌며 count[i]의 값을 출력하였다. 이중 for문이지만 결국 count 배열의 값을 모두 합친 N값만큼 반복되어 시간 복잡도는 여전히 O(N)이다.

package BOJ0726;

import java.util.Scanner;

public class BOJ_1427_SortInside {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String input = sc.next();
		int[] count = new int[10];
		for (int i = 0; i < input.length(); i++) {

			int c = input.charAt(i) - '0';
			count[c]++;
		}

		for (int i = 9; i >= 0; i--) {
			for (int j = 0; j < count[i]; j++) {
				System.out.print(i);
			}
		}

	}

}