[BOJ] 백준 2751번 : 수 정렬하기 2 (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

 

비슷한 문제

-2750번 수 정렬하기 문제

-10989번 수 정렬하기 3 문제

 

풀이1

2750번 수 정렬하기 문제와 N의 범위를 제외하면 완전히 같은 문제였습니다. 저는 처음에 같은 문제라 생각하여, Arrays.sort()를 사용하였지만, 시간초과가 발생하였습니다.

왜 그런지 알고보니, 제가 간과하던 것이 있었습니다. 바로, 퀵 정렬은 평균적으로 O(NlogN)인 것이지, 최악의 상황에는 O(N^2)가 가능하다는 것이었죠.

백준 게시판에서 2751번과 관련하여 자세하게 쓴 글이 있으니, 참고하실 분은 아래 링크를 클릭해 보시면 되겠습니다.

https://www.acmicpc.net/board/view/31887

글 읽기 - ★☆★☆★ [필독] 수 정렬하기 2 FAQ ★☆★☆★

 

위 글을 요약하자면, Arrays.sort에 경우, primitive type array(일반적인 int[]나 char[] 등)에 대해서 정렬을 수행할 때, 최악의 상황에서 시간 복잡도가 O(N^2)이라고 합니다. 따라서, Collections.sort를 사용하면 위 문제를 해결할 수 있습니다.

 

소스코드 - Collections.sort

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
 
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> arr = new ArrayList<>();
 
        for (int i = 0; i < N; i++) {
            arr.add(Integer.parseInt(br.readLine()));
        }
        
        // Arrays.sort가 아닌 Collections.sort를 사용한다.
        Collections.sort(arr);
 
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            sb.append(arr.get(i) + "\n");
        }
 
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}
 

 

풀이2

추가적으로 좀 더 알아보니, 상당히 유용한 정보를 얻을 수 있었습니다.

바로, java의 Arrays.sort는 worst case의 경우 속도가 Arrays.sort(int) < Arrays.sort(Integer)라는 것입니다!

타입이 primitive일 때 java의 Arrays.sort는 Quick sort를 사용하지만, Integer와 같은 객체일 때는 Merge sort를 사용하기 때문이죠.

Quick sort의 worst case는 모든 요소가 이미 정렬되어 있는 경우인데, 여기서 시간복잡도는 O(N^2)가 되는 반면, Merge sort의 worst case인 경우에서 시간복잡도는 O(NlogN)이기때문에 Arrays.sort(Integer)를 사용하면 위 문제를 해결할 수 있습니다.

위 내용을 자세하게 보실 분은 아래 링크를 참조 바랍니다.

https://codeforces.com/blog/entry/46756

Java: Arrays.sort(Integer) vs Arrays.sort(int) with Examples - Codeforces

 

소스코드 - Arrays.sort(Object)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
 
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());
        Integer[] arr = new Integer[N];
 
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        // 타입이 primitive가 아닌, Object이다.
        Arrays.sort(arr);
 
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            sb.append(arr[i] + "\n");
        }
 
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.