[Java] 백준(실버-5) 2751번 - 수 정렬하기 2

입출력 예시

Input

5
5
4
3
2
1

Output

1
2
3
4
5

문제 풀이

---

이 문제는 sort() 메소드를 이용해 오름차순 정렬을 해야 한다.
먼저 단순하게 Arrays.sort() 메소드를 이용해 문제를 풀어보니, 정답 처리가 되었다.

Arrays.sort()의 정답처리?

이전의 백준에서는 Java, Java(Open JDK), Java11로 언어 분류가 나뉘어 있었는데, 최근에 Java가 Java8로 명칭이 변경되었다.
찾아보니 당시 Java8에서 Arrays.sort()를 이용했을 때 시간초과가 나도록 유도된 것 같다고 한다.
그런데 Java11에서는 Java8과 다르게 다른 위치부터 피벗이 잡히기에 정렬방식이 정답처리될 수 있다고 한다.
그래서 동일한 코드로 문제 제출 언어를 Java8로 바꾸어 제출하니 시간초과가 발생하였다.

Collections.sort()를 활용한 정렬 활용

그렇다면 Arrays.sort() 말고 다른 정렬방식으로 시간초과를 해결해야 한다.
배열을 정렬하는 Arrays.sort()와 컬렉션을 정렬하는 Collections.sort()를 사용하는데, 무엇을 사용해야 할까?
Arrays.sort()와 Collections.sort()는 무슨 차이가 있는지 궁금해서 찾아보았다.

Arrays.sort()와 Collections.sort()의 차이점

-	정렬방식	시간복잡도
Array.sort()	Dual-Pivot-Quick-sort	평균일 경우 O(nlog(n)), 최악일 경우 O(n^2)
Collections.sort()	Tim-Sort	평균 및 최악일 경우 O(nlog(n))

Dual-Pivot-Quick-sort은 2개의 피벗을 사용하여 정렬을 수행하며, 퀵정렬은 평균적으로 O(NlogN), 최악일 경우 O(n^2)의 시간복잡도를 가진다. 그리고 Tim-Sort는 합병정렬을 기반으fh 일정 크기 이하의 부분 리스트에 대해서는 이진 삽입 정렬을 수행한다. 평균, 최악 모두 O(nlog(n))의 시간복잡도를 가진다.

상황에 따라 적절히 사용하는 것이 좋겠지만, 최악일 경우에는 O(nlog(n))의 시간복잡도를 가지는 Collections.sort()가 더 빠르다.
Collections.sort() 메소드를 이용해 문제를 풀어보자.

int N = Integer.parseInt(br.readLine());
ArrayList<Integer> asc_list = new ArrayList<>();

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

Collections.sort(asc_list);

for(int n : asc_list) bw.write(n+"\n");

먼저 N을 입력받고 Arraylist에 N개의 입력받은 수를 저장하고, Collections 패키지의 sort() 메소드를 이용해 오름차순으로 정렬한다.
Arrays.sort() 작성코드와 동일하게 언어를 Java8로 제출하니 시간초과 발생없이 정답처리가 되었다.

작성코드

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
        int N = Integer.parseInt(br.readLine());
        ArrayList<Integer> asc_list = new ArrayList<>();

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

        Collections.sort(asc_list);

        for(int n : asc_list) bw.write(n+"\n");

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

회고

• Arrays 및 Collections 패키지의 sort() 메소드의 차이점에 대해서 공부할 수 있었다.
• Arrays.sort()는 Java8에서 정답처리가 되지 못했으나, Collections.sort()는 Java8에서 정답이 되었다.
• Java8과 Java11에서의 sort() 메소드 정렬방식에 차이가 있음을 알게되었다.
• Arrays.sort() 정렬방식인 Dual-Pivot-Quick-sort과 Collections.sort() 정렬방식인 Tim-sort에 대해서 더 알아보고 공부해야겠다.

참고

• Java8과 Java11 비교 출처
• sort() 비교 출처