백준 | 정렬 섹션 - 10989번. 수 정렬하기 3

10989번. 수 정렬하기 3

문제

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

입력

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

출력

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

[1차] 내 코드 (시간 초과)

• 입력은 Scanner로 받고, Arrays.sort()로 정렬을 처리했는데 시간초과가 떴다.

import java.util.Arrays;
import java.util.Scanner;

/* 백준 10989번. 수 정렬하기 3
 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
*/
public class Main {


    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();

        int[] arr = new int[n];
        for(int i = 0; i<n; i++) {
            arr[i] = kb.nextInt();
        }
        //정렬
        Arrays.sort(arr);
        for(int x : arr) {
            System.out.println(x);
        }

    }
}

📍입출력 성능도 좋은 것 택해야 한다.

• 이 문제는 입출력 성능도 좋은 것을 택해야 한다.
• Scanner로 쓰면 내부적으로 자체 정규식 검사 과정에서 시간이 엄청 소요되기 때문에 '시간 초과'가 발생할 수 밖에 없다. 그렇기 때문에 BufferedReader 를 쓰는 것을 디폴트로 해야한다. 또한 출력도 BufferedWriter 또는 StringBuilder 를 이용하여 출력해야 한다.

[2차] 내 코드 * CountingSort를 사용해야 함

import java.io.*;

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

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

        int count[] = new int[10001];
        for(int i=0; i<N; i++) {
            count[Integer.parseInt(br.readLine())]++;
        }

        for(int i=1; i<10001; i++) {
            while(count[i] > 0) {
                sb.append(i).append('\n');
                count[i]--;
            }
        }

        System.out.println(sb);
    }
}