[백준] 10989번. 수 정렬하기 3 (Java)

[문제 바로가기] https://www.acmicpc.net/problem/10989

문제

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

입력

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

출력

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

※ 주의사항

1. Java의 시간 제한은 3초이다.
2. Java의 메모리 제한은 512MB이다.

풀이

1. 카운팅 정렬을 사용하기로 했다.
2. 입력되는 수의 범위는 10000보다 작거나 같은 자연수 (0 <= n <= 10000)
3. cnt[]배열을 만들어서 입력되는 수을 index로 하여 카운팅
4. 그러나 백준에서는 시간초과가 발생..

이유를 찾아보니 입출력의 성능과 출력 성능 때문이었다.

Scanner는 내부적으로 자체 정규식 검사 과정을 하기 때문에 시간이 엄청 소요가 되서 '시간 초과'가 발생할 수 밖에 없었다.

그래서 BufferedReader와 Stringbuilder을 이용해 값을 입력받고 출력했다.

• BufferedReader 입력 유의사항

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());

1. 기본적으로 한 줄을 통째로 입력받는 방식 사용

2. readLine() 메서드는 값을 읽어올 때, String값으로 개행문자 포함해 한줄로 전부 읽어오는 방식이다.

   • readLine() 메소드는 IOException을 발생시키기 때문에 throws IOException를 해줘야 한다.

3. read() 메서드는 값을 읽어올 때, int값으로 변형하여 읽어오는 방식

   • 예를 들어 input.txt에 저장된 1이라는 숫자를 read()를 통해 읽어오면 int형 숫자 1을 읽어오는 것이 아닌, txt형식으로 저장된 ASCII 형식의 문자값 '1'을 읽어오는 것이므로 결국 int값으론 49를 읽어오는 것이 된다.
   • 이것을 해결하려면 Integer.parseInt()를 사용한다.

코드

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

public class Main {

	public static void main(String[] args) throws IOException {

		//카운팅 정렬
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
	
		//입력되는 n <= 10000인 '자연수'이므로 입력 범위 0 ~ 10000
		int[] cnt = new int[10001];
	
		for(int i = 0; i < N; i++) {
			// 해당 인덱스의 값을 1 증가
			cnt[Integer.parseInt(br.readLine())]++;
		}
		
		StringBuilder sb = new StringBuilder();
		
		for(int i = 1; i < 10001; i++) {
			while(cnt[i] != 0) {
				sb.append(i).append("\n");
				cnt[i]--;
			}
		}
		System.out.println(sb);
	}
}