[Algorithm] BOJ 문제, 정렬

BOJ 2750, 2751 수 정렬 문제를 풀면서 여러 정렬 알고리즘에 대해 알아둘 필요를 느끼게 되었습니다.

이번 포스트에서는 2751에서 사용된 정렬 알고리즘에 대해 학습하고 여러 정렬 알고리즘에 대해서는 이어질 다음 포스트에서 자세히 다루겠습니다.

 

문제 원인 파악

2750 문제와 달리 2751은 Java의 Arrays.sort() 를 사용하면 시간초과가 날 수 있습니다.

Arrays.sort()의 경우 dual-pivot Quicksort 알고리즘을 사용한다고 합니다.

이 알고리즘은 평균 시간복잡도가 \(O(nlogn)\)으로 매우 빠른 알고리즘이지만 최악의 경우는 \(O(n^2)\)이기 때문에 주의해야 합니다.

 

그렇기 때문에 최악의 경우에도  \(O(nlogn)\) 혹은 \(O(n)\) 에 가까운 정렬 알고리즘을 사용해야 합니다.

 

해결법은 Collection.sort()

2751 문제에서는 Collections.sort()를 사용하면 됩니다. Collections.sort()는 Timsort입니다.

Timsort의 경우 합병 및 삽입 정렬 알고리즘을 사용합니다. 이렇게 두 가지가 섞여 있는 정렬 알고리즘을 hybrid sorting algorithm 이라고 하는데, 합병 정렬(Merge Sort)의 경우 최선, 최악의 경우 모두 \(O(nlogn)\)을 보장하고 삽입 정렬(Insertion sort)의 경우 최선의 경우는 \(O(n)\), 최악은 \(O(n^2)\)입니다. 두 정렬 모두 안정 정렬(stable sort) 이기 때문에 Timsort를 hybrid stable sorting algorithm이라고도 합니다.

 

즉, 합병 정렬의 최악의 경우와 삽입 정렬의 최선의 경우를 혼합한 알고리즘이 Timsort라는 것입니다. 실제로 Python이나 기타 정렬 알고리즘에서 많이 쓰이는 알고리즘이기도 합니다.

 

또한, 시간 복잡도 \(O(n)\) ~ \(O(nlogn)\)을 보장한다는 장점이 있습니다. 다만, Collections.sort()로 Timsort를 사용하고자 한다면 가장 쉬운 방법으로 기본형 타입(primitive type)의 배열이 아닌 참조형 타입(reference type)의 List(ArrayList, LinkedList 등)의 자료구조를 사용해야 합니다.

 

---

2751 문제를 다음의 세 가지 방법으로 풀이하여 성능을 비교해보록 하겠습니다.

 

1. Scanner + Collections.sort

2. BufferedReader + Collections.sort

3. BufferedReader + Counting.sort

 

1번 코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        int N = sc.nextInt();
        ArrayList<Integer> list = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            list.add(sc.nextInt());
        }
        Collections.sort(list);

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

 

2번 코드

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

public class test {
    public static void main(String[] args) throws Exception {
        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 num : list) {
            sb.append(num).append('\n');
        }
        System.out.println(sb);
    }
}

 

3번 코드

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

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

        boolean[] arr = new boolean[2000001];

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

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

        for (int i = 0; i < arr.length; i++) {
            if(arr[i]){
                sb.append((i - 1000000)).append('\n');
            }
        }
        System.out.println(sb);
    }
}

 

 

아래서부터 위로 1~3 코드의 풀이입니다.(중간 컴파일 에러는 클래스 이름을 Main으로 변경하지 않아서 발생함.)

1번의 방식보다 2번의 방식이 약 2배가량 빠르고 2번의 방식보다 3번의 방식이 2배가량 빠른 것을 확인할 수 있습니다.

또한 메모리도 절약이 되는 것을 확인할 수 있습니다.

 

3번의 경우, 수가 중복되지 않으므로 boolean 배열에 입력 받은 값을 index로 사용하는 방식입니다. 직접 비교 정렬이 아니므로 시간복잡도는 \(O(n)\)으로 배우 빠릅니다. 

---

여러가지 정렬에 대한 학습은 다음 포스트에서 더 자세하게 개념적으로 다루도록 하겠습니다.