백준 10989 : 수 정렬하기 3

8122 단어 백준백준

문제

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

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

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

접근

어렵진 않지만 상당히 흥미로운 문제였다. 단순히 접근하면 10,000,000크기의 배열을 만들어 모든 수를 입력받은 뒤 정렬하여 출력하면 되지만, 메모리와 시간 제한이 아주 작으므로 이러한 방법은 용납되지 않는다.
입력 받을 수의 최대값이 10,000이므로 10,000크기의 배열을 만들고, 비트마스킹 하듯이 입력받은 수의 인덱스에 해당하는 배열값을 하나 증가시켜주면 된다. 출력은 해당 배열의 인덱스가 0이 아닐 때 배열 값만큼 인덱스 값을 출력해주면 된다.
제한 시간이 적으므로, JAVA로 풀기 위해선 BufferedReader와 BufferedWriter를 사용해야 하는 점도 중요했다.

코드

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(bf.readLine());
		int [] count = new int[10001];
		
		for(int i = 0; i < n; i++) {
			count[Integer.parseInt(bf.readLine())]++;
		}
		
		for(int i = 0; i < 10001; i++) {
			if(count[i] != 0) {
				for(int j = 0; j < count[i]; j++) {
					bw.write(i + "\n");
				}
			}
		}
		
		bw.flush();
		bw.close();
	}
}

좋은 웹페이지 즐겨찾기