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

Ga0·2023년 4월 21일
1

baekjoon

목록 보기
35/137
post-custom-banner

문제 해석

  • 첫번째 줄에 입력받는 숫자의 개수(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();


    }
}

결과(맞은)

느낀점

  • 이번 문제는 문제 자체가 어렵다기보단 해당 문제에 쓰이는 알고리즘에 대해 공부하는 시간을 가졌다.
  • Collections.sort()는 처음보는 거라 전혀 쓸 생각을 하지 못했는데 덕분에 공부가 되는 시간이었던 것 같다.
post-custom-banner

0개의 댓글