JAVA 백준 문제풀이 (19) 2751: 수 정렬하기2

 

 

쉽게 풀려면 한 없이 쉬운 문제인데 어렵게 풀려면 어려워지는 문제이다.

 

쉽게 푸는 방법 : 내장 함수 Collections.sort() 사용하기.

어렵게 푸는 방법 : 직접 병합 정렬(Merge Sort) 작성해서 풀기.

 

그런데 나는 정렬 알고리즘에 대한 개념이 전혀 없는 상태에서 이걸 퀵 정렬(Quick Sort)로 풀겠다고 열심히 공부해서 작성했는데..

그렇다.. Quick Sort는 이런 오름차순 정렬에는 거품 정렬이나 다를 바 없는 최악의 성능 O(N^²)의 시간 복잡도를 갖게 되는 것이이였다..

따라서 시간 초과 ^^ ~~

 

3시간 쥐어짜서 배운 결과가 실패라니 허무해서 중간값 퀵소트(Median of Three QuickSort)도 배워서 시도해봤으나 역시나 실패.

난 오늘 반나절을 이미 정렬 알고리즘 공부에 보냈기 때문에 도저히 병합 정렬까지 새롭게 학습하고 싶지 않아서.. 그냥 쉬운 길을 택했다.

병합 정렬은 나중에 배워보는 걸로..

 

 

 

 

* 입력은 반드시 BuffuredReader로 받아야하고 출력도 반드시 StringBuilder나 BufferedWriter로 내보내야한다. (시간 초과)

* Arrays.sort()는 three pivot quicksort의 알고리즘을 사용한 메서드라서 Arrays.sort()도 시간 초과.

* 퀵 정렬 자체가 알고리즘 문제에서 저격 당하는 경우가 많아 사용하지 않는 것이 좋다고 한다. 

 

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

public class temp2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        ArrayList<Integer> arr = new ArrayList<>();
        StringBuilder sb = new StringBuilder();

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

        Collections.sort(arr);

        for (int i = 0; i < arr.size(); i++) {
            sb.append(arr.get(i)).append('\n');
        }

        System.out.println(sb);
    }
}