[BOJ] 2751번 - 수 정렬하기 2

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

2751번: 수 정렬하기 2

---

이 문제는 Arrays.sort() 로 하면 시간 초과가 발생한다

• Arrays.sort()는 primitive arrays에 대해 Dual-Pivot Quicksort를 수행한다
• 이는 평균 시간복잡도가 O(nlogn)이지만 최악의 경우 시간복잡도는 O(n^2) 가 된다
• 따라서 이 문제에서는 O(n^2)를 못하게 해서 시간 초과가 발생한다ㅠ

 

 

 

그래서 나는 2가지의 방식으로 성능을 개선했다!

 

1. Collections.sort()

• 이 문제를 풀기 위해서는 최악의 경우에도 O(nlogn)을 보장하거나, O(n)에 가까운 정렬 알고리즘을 사용해야한다
• Collections.sort()은 Object type arrays에 대해 Merge Sort 보다 향상된 Tim Sort 를 수행한다
• Tim sort 란 합병정렬의 최악의 경우와 삽입정렬의 최선의 경우를 짬뽕한 알고리즘으로 시간복잡도는 O(n) ~ O(nlogn) 을 보장한다

이제 될 거라고 생각했는데 또 시간초과가 발생했다,,,

 

 

2. StringBuilder

문제는 출력 방법이었다

String s = "";
for(int i=0;i<arr.length;i++) {
	s += arr[i];
}
System.out.println(s);

원래는 이런식으로 했는데 시간 초과가 발생했다

그래서 StringBuilder를 사용하는 방식으로 수정했다

 

StringBuilder는 String과 문자열을 더할 때 새로운 객체를 생성하는 것이 아니라 기존의 데이터에 더하는 방식을 사용하기 때문에 속도도 빠르며 상대적으로 부하가 적다

 

 

 

자바 코드)

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<Integer> arr = new ArrayList<>();
        for(int i=0;i<n;i++) {
            arr.add(scanner.nextInt());
        }
        Collections.sort(arr);
        StringBuilder sb = new StringBuilder();
        for(int num : arr) {
            sb.append(num).append("\n");
        }
        System.out.println(sb);
    }
}