문제

문제는 간단한 오름차순 정렬 문제이다.
Arrays.sort()를 사용해서 해결했다.

문제 풀이

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));
        int n = Integer.parseInt(br.readLine());
        Integer[] numbers = new Integer[n];
        for(int i=0;i<n;i++){
            numbers[i] = Integer.parseInt(br.readLine());
        }
        // 오름차순 정렬
        Arrays.sort(numbers);
        for(int i=0;i<n;i++){
            System.out.println(numbers[i]);
        }
    }
}

---

시간 복잡도

Arrays.sort()

그렇다면 Arrays.sort()의 시간 복잡도는 어떻게 될까?

Arrays.sort()는 인자의 타입에 따라서 사용되는 알고리즘이 다르다.

• 원시 타입인 경우 (ex. int, double)
• Object 타입인 경우 (ex. Integer)

1. 원시 타입인 경우

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Arrays.html

Arrays.sort()의 알고리즘은 Dual-Pivot Quicksort으로 기존의 one-pivot Quicksort를 개선하여 속도가 향상된 알고리즘이다.
(pivot을 2개 두고 3개의 구간을 만들어 퀵 정렬을 진행하는 알고리즘)

더 자세하게 코드를 살펴보면, Arrays.sort()에서 DualPivotQuicksort.sort()를 호출하는 것을 볼 수 있다.

그리고 DualPivotQuicksort에는 sort 메서드가 오버로딩되어 있으며 인자에 들어오는 배열의 크기에 따라 정렬 방법을 다르게 한다는 것을 알 수 있다.

• 배열의 크기가 286 이상일 경우 MergeSort를 수행한다.
• 배열의 크기가 286 보다 작은 경우 QuickSort를 MergeSort보다 우선 수행한다.
• 배열의 크기가 47보다 작은 경우 InsertionSort를 QuickSort보다 우선 수행한다.
• byte 배열의 크기가 29보다 큰 경우 CountingSort를 InsertionSort보다 우선 수행한다.
• short, char 배열의 크기가 3200보다 큰 경우 CountingSort를 QuickSort보다 우선 수행한다.

왜 이런 식으로 여러 알고리즘을 나누어서 사용하는가? 이 블로그에서 자세히 설명해주셨는데 이는 공간 복잡도 때문이다.

위의 여러 Sort 알고리즘 중에서 가장 시간 복잡도가 작은 것은 CountingSort이다. 하지만 CountingSort는 추가적인 배열을 하나 더 생성해야 하기 때문에 공간 복잡도가 크다. 그러므로 short, char 배열의 크기가 3200 보다 큰 경우에만 CountingSort를 사용한다.

[이미지 출처]
https://lamfo-unb.github.io/2019/04/21/Sorting-algorithms/

---

2. Object 타입인 경우

• TimSort를 사용한다.
• user가 별도로 설정하는 것이 아니면, ComparableTimSort.sort()를 사용한다.
• 거의 다 정렬되어 있는 경우 (Best) - O(n)
• 거의 정렬되어 있지 않은 경우 (Worst) - O(nlog(n))

Collections.sort()

• TimSort를 사용한다.

---

개선할 점

1. StringBuilder 사용

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

public class Main {
    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++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i]);
            if(i != arr.length-1) sb.append("\n");
        }
        System.out.println(sb.toString());

    }
}

• 코드는 거의 비슷하지만, 마지막에 출력할 때 StringBuilder를 사용했다.
  
  

2. Counting 정렬 응용

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
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());
        
		boolean[] arr = new boolean[2001];
		for(int i = 0; i < N; i++) {
			arr[Integer.parseInt(br.readLine()) + 1000] = true;
		}
		
		for(int i = 0; i < 2001; i++) {
			if(arr[i]) {
				sb.append(i - 1000).append('\n');
			}
		}
		System.out.println(sb);
	}
}

• arr의 크기가 2001인 이유는 입력되는 값이 절댓값 1000보다 작거나 같은 정수이기 때문이다.(중복 x)
• -1000~1000의 범위이기 때문에 Integer.parseInt(br.readLine()) + 1000를 해주는 것이다.
  ex) -1000이 입력된 경우, arr[0] = true여야 하기 때문에
  
  

이 블로그에서 다양한 방법으로 문제를 푸셨고, 각 풀이에 대한 속도를 측정하셨다. 이 문제에서는 어떤 정렬로 푸는 게 성능에 크게 영향을 주진 않았고, 오히려 StringBuilder나 BufferedReader의 사용유무가 더 중요했던 것 같다.

---

[참고]
https://javanitto.tistory.com/6
https://javanitto.tistory.com/7
https://sabarada.tistory.com/138
https://onlyfor-me-blog.tistory.com/317