[백준] 2751번 수 정렬하기 2 - 정렬(1) [JAVA]

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

---

     문제

     문제 풀이

• 정렬 문제다. 한번 틀림😇
• 삽입 정렬의 시작 복잡도는 O(n²)이다. 너무 오래 걸린데!!!
  단순히 출력문 문제일줄 알았는데 아니였다.
• Tim Sort로 풀어야하는 문제이다. Merge Sort(합병 정렬) + Insertion Sort(삽입 정렬)이 합쳐진 정렬이다.
  아직 정확히 몰라서 구글링을 했다...
• 푼 방법
  1) 시간을 지키는 게 매우 중요한 문제니까, BufferedReader, StringBuilder를 사용하자.
  2) Array.sort()는 내부적으로 quickSort, timSort를 사용한다. 따라서 사용하면 안됨! (정렬 종류들에 대한 정리는 차차 해보자.)
  3) Collections.sort()는 내부적으로 timSort만 사용한다. 따라서 Collections.sort()로 정렬하면 된다.
  *구현해서 사용하고 싶었는데, 생각보다 너무 길어져서 포기했다🥹 따로 게시글로 직접 구현해보자.

---

     JAVA code[1] - Insertion Sort (Incorrect)

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

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

        for (int i = 1; i < N; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }

        for (int i = 0; i < N; i++) {
            System.out.println(arr[i]);
        }
    }
}

     JAVA code[2] - Tim Sort (Correct)

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class baekjoon2751 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

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

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

        Collections.sort(list);

        for (int value : list) {
            sb.append(value).append("\n");
        }
        System.out.println(sb);
    }
}