백준 | 2751 : 수 정렬하기 2 (Java)

문제에 대한 자세한 정보는 백준 | 2751번 : 수 정렬하기 2에서 확인할 수 있다.

---

풀이

ArrayList에 입력받아서 Collections.sort()를 사용했다.

Collections.sort()는 Timsort로 삽입, 합병 정렬을 결합한 방식의 알고리즘을 사용하는데 이런 방식의 알고리즘을 hybrid sorting algorithm이라고 한다.
Collections.sort()는 시간복잡도 O(n) ~ O(nlogn)을 보장한다고 한다.

배열을 생성해 Arrays.sort()를 사용하지 않은 이유는 위와 같다. Arrays.sort()는 최악의 경우 시간복잡도가 O(n²)이기 때문이다.

그런데 위 방법으로 풀고 다른 풀이들을 찾아봤는데 전혀 생각도 못한 방법의 풀이를 발견해서 슬펐다. 입력의 중복이 없으므로 배열의 index를 사용하면 시간복잡도 O(n)으로 풀이할 수 있는데 이걸 생각하지 못했다.

입력으로 주어지는 수가 절댓값이 1,000,000보다 작거나 같은 정수이므로 2,000,001 길이를 가지는 배열을 생성하면 된다.
0이 주어지면 arr[1000000]에 저장되는 구조이다.

---

소스코드

• Collections.sort() 사용

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        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 i = 0; i < n; i++) {
            bw.write(String.valueOf(list.get(i)) + "\n");    
        }

        br.close();
        bw.close();
    }

}

• 배열의 index 사용

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        boolean[] arr = new boolean[2000001];

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

        for (int i = 0; i < arr.length; i++) {
            if (arr[i]) {
                bw.write(String.valueOf(i - 1000000) + "\n");
            }
        }

        br.close();
        bw.close();
    }

}

---

메모리, 시간

Collections.sort() 사용

메모리 : 172544KB
시간 : 1816ms

배열의 index 사용

메모리 : 142008KB
시간 : 960ms