백준 알고리즘 문제(82) - 소트인사이드

단순하게 정렬하는 문제다. 내림차순으로 정렬해야하는데
2341을 입력받으면, 4321을 출력해야한다.

이 문제는 countingsort를 사용하지 않을 것이다. N의 범위가 1,000,000,000이나 되므로 공간을 낭비하기 때문이다. 그렇다면 내가 생각할 수 있는 방법은 두 가지다.

1. N%10을 배열에 저장하고 N/10을 하는 반복문을 통해서 N이 0이 되기 직전까지 반복한다음 Arrays.sort 혹은 Collections sort를 해주고 거꾸로 출력해가는 것이다.

2. N을 문자열로 입력받아서 charAt()으로 각 문자를 읽어들여서 int형으로 바꾼뒤에 정렬해주는 방법이다.

1번은 분명 시간복잡도가 O(N^2) or O(nlogn)이고, 최선의 경우에 O(n)일테니, 2번 방법을 사용해주겠다.

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


public class java_io {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args) throws IOException {
		String N = br.readLine();
		int[] arr = new int[N.length()];
		for(int i=0; i<N.length(); i++) {
			arr[i] = N.charAt(i)-'0';
		}
		
		Arrays.sort(arr);
		
		for(int i=arr.length-1; i>=0; i--) {
			System.out.print(arr[i]);
		}
		
	}
	
	
}

분명히 더 효율적인 방법은 ArrayList를 활용하거나, StringBuilder를 사용해 출력하는 것이다. 나는 charAt을 이용했지만 N.toCharArray()를 이용해서 아스키코드 값으로 저장된 char[]배열을 만들고 정렬해서 출력하는 방법도 있다.

아 그리고, countingsort를 이용해서 메모리를 낭비한다고 생각했는데, int가 아니라 문자열로 입력받으면 10개의 공간만 만들면 되므로, 좋다고 생각한다.