백준 2751 수 정렬하기2 [JAVA]

Ga0·2023년 4월 21일

baekjoon

목록 보기

35/148

문제 해석

첫번째 줄에 입력받는 숫자의 개수(N)을 입력받고, 두번째 줄부터는 N개 만큼의 숫자를 줄별로 입력받는다.
입력받은 숫자들을 작은 수 -> 큰 수 로 정렬하여 출력하면 되는 문제이다.

코드(틀린)


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

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());

        int[] arr = new int[N];

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

        br.close();

        Arrays.sort(arr);

        for(int i = 0; i < N; i++){
           bw.write(arr[i] + "\n");
        }

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


    }
}

문제를 처음 봤을 때는 간단하다고 생각했고 그래서 그냥 쉽게 풀어 위의 코드를 제출하였다.

결과(틀린)

시간초과.. 이상하다 싶었다 (실버문제가 이렇게 간단히 풀리는게 이상했는데...)

틀린 이유

틀린 코드를 보면 Arrays.sort()를 사용했는데, 이 Arrays.sort() 의 경우 dual-pivot Quicksort 알고리즘을 사용한다.
dual-pivot Quicksort 알고리즘은 평균 시간복잡도가 O(nlogn) 이고, 최악의 경우 시간복잡도는 O(n2) 이라는 이다

Quick Sort

Dual Pivot Quick Sort

(참고)퀵정렬 vs 듀얼 피봇 퀵 정렬

아무튼 이러한 이유로 최악의 경우에도 O(nlogn) 를 보장하는 정렬 알고리즘을 사용해야한다.
그 방법으로는 Collctions.sort()를 사용해야한다.
Collections.sort()는 Timsort를 사용하는데, Timsort는 삽입 정렬과 병합정렬을 결합한 알고리즘이다.

TimSort(팀정렬) 팀정렬에 대한 정보는 이 게시물을 보고 이해했다.
-> 추후에 나도 정리할 예정

코드(맞은)


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

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개열 중에 써야한다. Collections.sort()를 쓰기 위해 Arrays.sort보다 빠름
        ArrayList<Integer> list = new ArrayList<Integer>();

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

        br.close();

        Collections.sort(list);

        for(int i : list){
            bw.write(i + "\n");
        }


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


    }
}