문제 출처

단계별로 풀어보기 > 정렬 > 수 정렬하기 3
https://www.acmicpc.net/problem/10989

문제 설명

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하라.
(시간제한 3초)

접근 방법

단순하게 배열에 저장하고, Arrays.sort를 이용하여 오름차순 정렬하였다.

import java.io.*;
import java.util.Arrays;

public class 수_정렬하기_3{

    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[] arr = new int[N];

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

        Arrays.sort(arr);

        StringBuilder sb = new StringBuilder();

        for(int k : arr){
            sb.append(k).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

CountingSort 이용

import java.io.*;

public class 수_정렬하기_3_countingSort {
    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 count[] = new int[10001];

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

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

        br.close();

        StringBuilder sb = new StringBuilder();

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

알게된 점

결과는 2464ms로 제한 시간 안에 성공은 했으나, 생각보다 오래 걸린다.

다른 사람의 풀이를 보니 Conting sort를 이용하면 시간이 2/3로 줄어든다는 결과가 있어서 내일은 한 번 그렇게 Review를 해보려고 한다.

문제푼 흔적