[BOJ/Step12] 1427 : 소트인사이드 (JAVA)

www.acmicpc.net/problem/1427

1427번: 소트인사이드

---

문제

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

 

입력

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

 

출력

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

 

예제 입력 1

2143

 

예제 출력 1

4321

---

풀이

그냥 입력받은 수를 한자리씩 분리한 후 정렬하여 내림차순으로 줄바꿈 없이 출력하면 된다

1. 주어지는 수 n을 String s에 저장한다

2. s의 길이만큼의 배열을 만들고, s를 한자리씩 분리하여 저장한다.

   => charAt() , getNumericValue() 메소드 사용

3. 배열을 정렬한다. 0~9까지의 범위밖에 존재하지 않기 때문에 카운팅 정렬을 사용하였지만 다른 정렬도 상관 없다

4. 정렬된 배열을 거꾸로 출력한다.

 

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

public class B1427 {
	
	static void countingSort(int[] a, int n) {
		int max = a[0];
		for(int i = 0; i < n; i++) {
			if(a[i] > max)
				max = a[i];
		}
		
		int[] counting = new int[max+1];
		int[] b = new int[n];
		
		for(int i = 0; i < n; i++) counting[a[i]]++;
		for(int i = 1; i <= max; i++) counting[i] += counting[i-1];
		for(int i = n-1; i >= 0; i--) b[--counting[a[i]]] = a[i];
		for(int i = 0; i < n; i++) a[i] = b[i];
	}

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

		String s = br.readLine();
		int[] num = new int[s.length()];

		for(int i = 0; i < num.length; i++) {
			num[i] = Character.getNumericValue(s.charAt(i));
		}
		
		countingSort(num, num.length);
		
		for(int i = num.length-1; i >= 0; i--) {
			System.out.print(num[i]);
		}
	}
}