[백준] 2751 - 수 정렬하기 2 (Java)

https://st-lab.tistory.com/106?category=857114 

[백준] 2751번 : 수 정렬하기 2 - JAVA [자바]

*해당 포스팅은 상단에 링크된 포스팅을 바탕으로 개인 공부 목적을 위해 작성되었으므로 자세한 내용은 위 링크를 확인해 주시기 바랍니다.

---

 

역시나 선생님이 예상하신대로 나는 Arrays.sort를 썼지만 dual-pivot Quicksort에서 평균 시간 복잡도가 O(nlongn)이지만 최악의 경우 시간 복잡도가 O(n²)가 된다고 했는데 이 문제가 최악에 해당되는 경우였다. 자바 버전마다 시간 초과 여부는 다르다고 하셨지만 나는 그냥 안전하게 다른 경우를 배우기로 했다. 

 

1. Collections.sort()

Collections.sort()는 합병 정렬과 삽입정렬 알고리즘에서 파생된 Timesort 알고리즘을 사용한다.

출처 : 위키피디아

표에서 보는 것처럼 이 알고리즘은 시간 복잡도 O(n) ~ O(nlongn)를 보장한다는 것을 알 수 있겠다. 그리고 Collections.sort()를 사용할 때는 List 계열(ArrayList, LinkedList, ...)의 자료구조를 사용하면 된다!

 

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

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());

        ArrayList<Integer> list = new ArrayList<>();

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

        Collections.sort(list);

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

내가 이제 System.out에 익숙해졌는지 자꾸 StringBuilder를 쓸 수 있는데도 안 써서 의식적으로 다시 쓰려고 노력해야겠다. (반성)

 

 

2. Counting sort

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

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

        boolean[] arr = new boolean[200000001];

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

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

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

 

위에가 Counting sort인데 확실히 차이가 있었다. 선생님이 제출하신 내역을 보면 메모리도 시간도 다 줄었는데 나는 왜 메모리가 저 모양이지...? 아무튼 정렬 단계 풀면서 잘 정리해놔야겠다.