수 정렬하기 3

제출코드

class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int repetition = Integer.parseInt(br.readLine());
        int[] numbers = new int[repetition];
        for (int i = 0; i < repetition; i++) {
            numbers[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(numbers);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        for (int n : numbers) {
            bw.write(String.valueOf(n) + "\n") ;
        }

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

문제 자체는 쉽지만, 시간 제한을 지키기 위해선 더 빠른 코드가 필요하다.

모범답안

package baekjoon.array;

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

public class Main {

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

        /**
         *
         * 1. Arrays.sort() : 평균 O(nlogn) 의 시간복잡도를 보이지만
         * 최악의 경우 O(n2) 로 좋지 않는 성능이 될 수도 있음

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int[] numbers = new int[repetition];

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

         Arrays.sort(numbers);

         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

         for (int n : numbers) {
         bw.write(String.valueOf(n) + "\n") ;
         }

         bw.flush();
         bw.close();
         br.close();

         */

        /**
         * 2. 카운팅 정렬:  시간복잡도는 O(N + K) 이다.
         * K는 자릿수를 의미하는데 입력데이터가 K 보다 훨 씬 큰 경우,
         * 즉 데이터가 많으면 많을 수록 O(N) 에 가깝기 때문에 이상적으로는 O(N) 이라고 보아도 무방하다.
         *
         */
         int[] cnt = new int[10001];

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

        for (int i = 0; i < N; i++) {
            // 해당 인덱스의 값을 1 증가시킴
            cnt[Integer.parseInt(br.readLine())] ++;
        }

        br.close();

        StringBuilder sb = new StringBuilder();

        // 0은 입력범위에 없으므로 1부터 시작
        for (int i = 1; i < 10001; i++) {
            // i 값이 개수가 0이 될 때까지 출력 (빈도수를 의미)
            while (cnt[i] > 0) {
                sb.append(i).append('\n');
                cnt[i]--;
            }
        }
        System.out.println(sb);
    }
}

Arrays.sort()는 평균 O(nlogn)의 시간 복잡도를 보이지만 최악의 경우 O(n^2)로 좋지 않은 성능이 될 가능성이 있다.

시간제한이 빡세다면 인덱스를 사용하는 카운팅 정렬을 사용하면 된다.
입력값이 3,6,6이라고 가정해보자.
인덱스가 3,6인 곳에 누적 횟수를 값으로 넣는다.

배열을 순회하며 값이 있는 인덱스를 출력한다.
만약 값이 모두 1개라면, cnt[i]--; 을 할 필요가 없겠지만, 만약 2개 이상이라면 꼭 값을 빼주어야 한다.

카운팅 정렬을 사용하니 많은 자원과 시간을 아낄 수 있게 됐다.