[BOJ] 2751. 수 정렬하기2

문제

 

 

 

 

 

문제 풀이

 

 

안일하게 Array.sort() 돌렸다가 시간초과가 났었다.

검색해보니 Arrays.sort()는 dual pivot quicksort 알고리즘을 사용하기에 시간 초과가 난 것이라고 한다.

dual-pivot Quicksort 알고리즘은 평균 시간복잡도가 O(nlogn) 이고, 최악의 경우 시간복잡도는 O(n2) 이기 때문에..

N의 범위가 1,000,000까지로 꽤나 크다 보니 최악의 경우 시간복잡도가 O(nlogn)인 알고리즘을 활용해야 했다.

힙 정렬과 병합 정렬이 해당하는데 병합 정렬을 적용하여 풀이하였다.

 

 

 

 

 

 

 

병합정렬 풀이

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class BOJ2751 {
    public static int[] arr, tmp;
    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());
        arr = new int[n + 1];
        // 합치는 과정에서 정렬하여 원소를 담을 임시배열
        tmp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        merget_sort(1, n); // 병합정렬 수행하기
        for (int i = 1; i <= n; i++) {
            bw.write(arr[i] + "\n");
        }
        bw.flush();
        bw.close();
    }

    private static void merget_sort(int start, int end) {
        // 1. 분할
        if (end - start < 1)
            return;

        int mid = start + (end - start) / 2;

        // 재귀함수 형태로 구현
        merget_sort(start, mid);
        merget_sort(mid + 1, end);

        for (int i = start; i <= end; i++) {
            tmp[i] = arr[i];
        }

        // 2. 정복
        int k = start;
        // 2가지 그룹으로 병합 이후, 포인터 개념 사용하여 두 그룹 병합
        int index1 = start;
        int index2 = mid + 1;

        while (index1 <= mid && index2 <= end) { // 두 그룹을 Merge 해주는 로직
            // 두 그룹 병합
            // 양쪽 그룹의 index가 가리키는 값을 비교하여 더 작은 수를 선택해 배열에 저장
            // 선택된 데이터의 index 값을 오른쪽으로 한 칸 이동
            if (tmp[index1] > tmp[index2]) {
                arr[k] = tmp[index2];
                k++;
                index2++;
            } else {
                arr[k] = tmp[index1];
                k++;
                index1++;
            }
        }
        // 한쪽 그룹이 모두 선택된 후 남아있는 값 정리하기
        while (index1 <= mid) {
            arr[k] = tmp[index1];
            k++;
            index1++;
        }
        while (index2 <= end) {
            arr[k] = tmp[index2];
            k++;
            index2++;
        }

    }
}

 

 

 

Collections.sort() 풀이

 

일반적으로 배열을 정렬할 때는 Arrays.sort()를 주로 쓰고, List, Set과 같은 컬렉션을 정렬할 때에는 Collections.sort()를 쓴다.

이 둘의 정렬 방식에 따라 시간 복잡도도 달라지기 때문에 시간 제한(위 문제의 경우 2초)에 따라 실패할 수도 있다.

 

	사용 정렬	시간 복잡도
Arrays.sort()	Dual-Pivot Quicksort	평균 : O(nlogn) 최악 : O(n^2)
Collections.sort()	Timsort (삽입 정렬과 병합 정렬이 혼합된 정렬)	평균/최악 : O(nlogn)

 

위 문제에서는 최악이 O(nlogn)인 Collections.sort()를 써야 좀 더 빠른 성능을 낼 수 있고, 시간 제한을 초과하지 않을 것이다.

 

 

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

public class BOJ2751RE {
    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()));
        }

        br.close();

        Collections.sort(list);

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

 

 

 

 

참고

 

https://laugh4mile.tistory.com/175

[JAVA] 정렬에 대한 고찰 (Arrays.sort() 와 Collections.sort())

 

https://st-lab.tistory.com/276

자바 [JAVA] - 팀 정렬 (Tim Sort)