[백준알고리즘] 2751. 수 정렬하기 2 풀이 (Java)

❓ 문제

❗ 풀이

해당 문제는 시간 제약이 있었기 때문에 Arrays.sort()를 사용할 경우 시간초과 문제가 발생할 수 있다. (뒤에 Arrays.sort()를 사용하여 푸는 방법도 설명해두었다.)

Arrays.sort()의 경우 평균 시간복잡도가 O(nlogn)이고 매우 빠른 알고리즘이지만, 최악의 경우 시간복잡도는 O(n^2)이다. 따라서, Collections.sort()를 사용해 문제를 풀었다.

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

class Main { // SortAsc2
    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> numList = new ArrayList<Integer>();

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

        Collections.sort(numList);

        for(int item : numList) {
            sb.append(item).append('\n');
        }
        System.out.println(sb);
    }
}

List를 사용할 때 for문을  for(int item : numList) 사용할 수 있다는 점을 생각하자!! 

Arrays.sort()는 worst case의 속도가 Arrays.sort(int) < Arrays.sort(Integer)이다.

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

worst case일 때, Quick sort는 시간복잡도는 O(n^2)이지만, Merge sort는 시간복잡도가 O(nlogn)이기 때문에 Arrays.sort(Integer)를 사용해서 풀 수도 있다.

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

class Main { // SortAsc2
    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());
        int[] numArr = new int[N];

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

        Arrays.sort(numArr);

        for(int i = 0; i < N; i++) {
            sb.append(numArr[i]).append('\n');
        }
        System.out.println(sb);
    }
}

알고리즘을 이제 막 공부를 시작하고 있는 단계라 해당 알고리즘의 시간복잡도를 완전히 이해가 가진 않는다.

하지만 이렇게 하나씩 뭐라도 하다보면 성장하겠지...!!

 

 📌 참고

• https://dev-coco.tistory.com/151

 

🚩 Detail

• 날짜 : 2022.08.08 ~ 2022.08.10
• 단계 : 11단계 정렬
• 제목 : 수 정렬하기 2
• URL : https://www.acmicpc.net/problem/2751