[BOJ] 2751번 : 수 정렬하기 2

BOJ 2751번 - 수 정렬하기 2

🔒 문제

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

⌨ 입력

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

🖨 출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

📍 제한

• 시간 제한 : 2초
• 메모리 제한 : 256 MB

📚 예제

Ex)

• 예제 입력
• 5 5 4 3 2 1
• 예제 출력
• 1 2 3 4 5

📌 풀이

데이터의 최대 크기가 1,000,000이고 시간 제한은 2초이다.
우리는 1초에 100,000,000($10^8$)번 연산이 가능한 것을 안다.
제한 시간이 2초라면 200,000,000번의 연산이 가능하다.

1. O(N²)인 알고리즘 사용 ⛔️
   연산 횟수가 10¹²이 되고 이것은 $2*10^8$ 연산보다 크기 때문에 시간 초과가 발생한다.
2. O(NlogN)인 알고리즘 사용 ✅
   연산 횟수가 $2*10^7$이기 때문에 시간 초과가 발생하지 않는다.

🚨 주의할 점

1. python
   파이썬의 정렬 함수인 sort()와 sorted()는 O(NlogN)으로 최적화가 잘 된 함수라 주의할 점이 없다.
2. java
   Java에서는 정렬 방법이 2가지가 있다.
3. Java에서 배열과 리스트를 정렬할 때 사용하는 이 2가지 메서드의 내부 정렬 방식과 시간 복잡도 차이를 통해 무엇을 사용해야하나 생각해보자.

🔍 Java의 정렬 메서드 정리: Arrays.sort() vs Collections.sort()

Java에서 정렬을 수행할 때는 상황에 따라 Arrays.sort() 또는 Collections.sort()를 사용하게 되는데, 이 둘은 내부 구현 방식도 다르고, 시간 복잡도에도 차이가 있다.

메서드	정렬 방식	시간 복잡도
Arrays.sort()	DualPivotQuicksort	평균: O(n log n), 최악: O(n²)
Collections.sort()	TimSort (삽입정렬 + 병합정렬)	평균 & 최악: O(n log n)

✅ Arrays.sort()

• 사용 대상: int[], String[] 같은 기본 배열
• 정렬 알고리즘: DualPivotQuicksort
  • 일반적인 QuickSort보다 개선된 방식으로, 피벗을 2개 사용해서 분할
• 시간 복잡도:
  • 평균: O(n log n)
  • 최악의 경우: O(n²) (거의 정렬되어 있는 경우나 모든 값이 동일할 때 등)

🚨 Arrays.sort()는 기본형 배열에서 매우 빠르지만, 데이터 패턴에 따라 최악의 성능 가능성이 존재.

---

✅ Collections.sort()

• 사용 대상: ArrayList, LinkedList 같은 컬렉션(List) 객체
• 정렬 알고리즘: TimSort
  • 삽입정렬 + 병합정렬의 하이브리드
  • Python의 sorted()와 동일한 알고리즘
• 시간 복잡도:
  • 평균, 최악 모두 O(n log n)
  • 안정적인 정렬 성능을 보장

✅ Collections.sort()는 데이터 양이 크거나 정렬 안정성이 중요한 경우 유리함

---

📌 정리

• 빠른 속도가 중요한 경우 → Arrays.sort()
• 최악의 성능까지 고려해야 한다면 → Collections.sort()가 더 안정적
• 기본형 배열이면 Arrays.sort(), 객체형 리스트면 Collections.sort()를 사용하면 됨

---

ex)

// 기본형 배열 정렬
int[] arr = {5, 2, 3, 1};
Arrays.sort(arr);

// 리스트 정렬
List<Integer> list = new ArrayList<>(List.of(5, 2, 3, 1));
Collections.sort(list);

🔑 python 코드

import sys
input = sys.stdin.readline

N = int(input())
arr = []
for i in range(N):
    arr.append(int(input()))

arr.sort()

for i in range(N):
    print(arr[i])

🔑 java 코드

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        List<Integer> arr = new ArrayList<>();

        for(int i = 0; i < N; i++){
            arr.add(sc.nextInt());
        }

        Collections.sort(arr);

        for(int i = 0; i < N; i++){
            System.out.println(arr.get(i));
        }
        sc.close();
    }
}