최고의 개발자 (목표)

문제

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

입력

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

출력

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

코드

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 Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		
		int[] array = new int[10001]; // index => 해당숫자, 값  => 숫자의 갯수
		Arrays.fill(array, 0); // 배열 0으로 채우기
		
		for (int i = 0; i < N; i++) {
			array[Integer.parseInt(br.readLine())] += 1;
		}

		for(int i = 0; i < 10001; i++) {
			for(int j = 0; j < array[i]; j++) {
				bw.write(i + "\n");
			}
		}

		bw.flush();
		bw.close();
		br.close();
	}
}

풀이

시간을 최대한 줄이기 위해 bufferedReader와 bufferedWriter를 사용했다.

처음에는 Arraylist에 담고 Collections.sort()를 이용했는데 메모리 초과가 났다. 그래서 카운팅 정렬을 이용해 문제를 풀었다. 등장할 수 있는 수는 10000보다 작기 때문에 배열을 10001칸을 할당해주고 Arrays.fill을 이용해 0으로 채워준다. 잠깐 카운팅 정렬에 대해 얘기하자면,  index는 수가 되고 해당 index의 값은 수가 등장한 횟수가 된다. 즉 1이 한 번 나오면 array[1] = 1 이 되고, 1이 또 등장하면 array[1] = 2 가 된다.

따라서 입력을 받을 때 array[입력받은 수]에 1씩 더해준다. 그 후 array의 처음부터 출력해주면 된다.

만약 array[1] = 3이라면, 1이 3번 나왔다는 것이므로 출력할 때 1 + "\n" + 1 + "\n" + 1 이런 식으로 출력을 해야 한다.

따라서 이중 포문을 사용해서 첫 번째 포문으로는 array를 돌고, 두 번째 포문으로 각 인덱스에 저장된 값만큼 돌면서 현재 index를 bw에 저장한다. 그 후 마지막에 flush()를 이용해 한 번에 출력한다.