[백준 | Java] 2751 수 정렬하기 2

문제

---

첫 시도

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

public class _2751 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] number = new int[n];

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

        Arrays.sort(number);
        for (int result : number) {
            System.out.println(result);
        }
    }
}

시간초과로 실패
dual-pivot Quicksort 알고리즘을 사용하는 Array.sort()를 사용했지만,
평균 시간복잡도가 O(nlogn)이고
최악 시간복잡도는 O(n2)이기 때문에 퀵정렬이라고 무조건 좋은 게 아니였다.
=> O(n^2)이면 시간초과가 되는 문제다.

---

해결 방법

해결 방법엔 2가지가 있다.

• 최악의 경우에도 O(nlogn)을 보장하거나 혹은, O(n) 에 가까운 정렬 알고리즘을 사용해야한다.

  • Collections.sort() 사용
    Collections.sort()는 Timsort이며, 합병 및 삽입정렬 알고리즘을 사용하고 이를 hybrid sorting algorithm이라고 한다.
    합병정렬(Merge Sort)의 경우 최선, 최악 모두 O(nlogn) 을 보장하고.
    삽입정렬(Insertion sort)의 경우 최선의 경우는 O(n) , 최악의 경우는 O(n2) 이다.
    List계열(ArrayList, LinkedList 등)의 자료구조를 사용해 정렬해야한다.
    => 시간복잡도 참고
    선택정렬: O(n2)
    삽입정렬: O(n2)
    버블정렬: O(n2)
    합병정렬: O(nlogn)
    퀵정렬(평균): O(nlogn)
    퀵정렬(최악): O(n2)

• 출력으로 Stringbuilder를 사용해야한다.

  Stringbuilder는 String과 문자열을 더할 때 새로운 객체를 생성하는 것이 아니라 기존의 데이터에 더하는 방식을 사용하기 때문에 속도도 빠르며 상대적으로 부하가 적다.
  => 사용방법
  append()를 사용하여 StringBuilder에 값을 저장한다.
  저장되는 형태는 append(값) + append(값)인데, "값" + "값" 형태로 저장되어 값을 서로 붙인다.

수정한 코드

• 방법1: BufferedReader + Arrays.sort() + StringBuilder 사용

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

public class Main {
    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());
        int[] number = new int[n];

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

        Arrays.sort(number);

        for (int i = 0; i < n; i++) {
            sb.append(number[i] + "\n");
        }

        System.out.println(sb);
    }
}

• 결과:
  

• 방법2: BufferedReader + Arrays.sort() + StringBuilder 사용

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

public class Main {
    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> number = new ArrayList<>();

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

        Collections.sort(number);

        for(int result : number) {
            sb.append(result + "\n");
        }
        System.out.println(sb);
    }
}

• 결과: