문제 출처

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

문제 설명

N개의 수가 주어질 때, 오름차순으로 정렬하라.

접근 방법

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class 수_정렬하기_2 {
    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());

        List<Integer> list = new ArrayList<>();

        for(int i = 0; i<N; i++){
            int k = Integer.parseInt(br.readLine());
            list.add(k);
        }
        Collections.sort(list);

        StringBuilder sb = new StringBuilder();

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


    }
}

알게된 점

처음 문제를 풀 때, Arrays.sort를 이용하여 배열을 정렬하려 했으나, 이를 이용하면 시간 초과가 난다는 것을 보고, 다음과 같이 풀이했다.

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    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());

        List<Integer> list = new ArrayList<>();

        for(int i = 0; i<N; i++){
            int k = Integer.parseInt(br.readLine());
            list.add(k);
        }
        Collections.sort(list);

        for(int j : list){
            bw.write(j + "\n");
            bw.flush();
        }
        bw.close();
        br.close();


    }
}

하지만, 해당 풀이도 시간 초과가 났는데, 내가 생각하는 문제는 list 속의 자료형은 Integer(int) 인데, 결과를 출력할 때, bw.write(j + "\n"); 에서 자료형을 int -> String 으로 형변환을 하면서 시간 초과가 발생한 것 같다.

배열을 정렬하는 Arrays.sort의 경우 dual-pivot Quicksort를 이용하여 시간 복잡도가 최악의 경우 O(n^2)이 나온다. 해당 문제에서는 이 경우 시간 초과가 나오게 된다.

반면 Collections.sort의 경우 Timsort(합병 정렬 + 삽입 정렬)를 이용하기 때문에 시간 복잡도가 O(n) ~ O(nlogn)의 경우가 나온다.

문제푼 흔적