10989_수 정렬하기3 (JAVA)

10989번: 수 정렬하기 3

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

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

		int N = Integer.parseInt(br.readLine());

		int max = 0;
		int[] input = new int[N];
        
		for(int i=0; i<N; i++){
			input[i] = Integer.parseInt(br.readLine());
			max = Math.max(max, input[i]);
		}

		int[] counting = new int[max+1];
		int[] ans = new int[N];

		for(int i=0; i<N; i++){
			counting[input[i]]++; //카운팅 배열
		}

		for(int i=1; i<counting.length; i++){
			counting[i] += counting[i-1]; //누적
		}

		for(int i= input.length-1; i>=0; i--){
			ans[--counting[input[i]]] = input[i];
		}

		for(int i=0; i<N; i++){
			bw.write(Integer.toString(ans[i])+'\n');
		}

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

 

1. Scanner, Print는 모두 시간초과가 난다!

   BufferedReader, BufferedWriter를 이용했다.

 

2. 카운팅 정렬 이용해서 정렬 - 카운팅 정렬 관련 글 참고!

카운팅 정렬 (Counting Sort)