백준BOJ/Java/Python : 2750번 수 정렬하기

2750번 : 수 정렬하기 원본

알고리즘 분류

• 정렬

문제

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

입력

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

출력

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

풀이

• Arrays.sort() 함수 [Java]
  • Dual-Pivot Quick Sort 방식을 이용하는 정렬 함수이다.

Dual-Pivot Quick Sort 방식은 Quick Sort(퀵 정렬) 방식의 변형으로 Pivot를 2개를 사용해 3개의 영역으로 분할하여 영역별로 정렬해주는 방식이라고 한다. Quick Sort처럼 평균 시간 복잡도는 O(NlogN)으로 최악의 경우 O(N^2)을 갖는다.

1. 먼저 왼쪽 끝 숫자를 LP로, 오른쪽 끝 숫자를 RP로 설정하고 LP > RP인 경우 서로의 위치를 바꾸어 준다.
2. LP와 RP를 기준으로 3개의 영역으로 나눈다. X < LP / LP < X < RP / RP < X로 나누어진다.
3. 나누어진 영역 별로 Dual-Pivot Quick Sort를 진행한다.

소스 코드

Java

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

public class Baek2750 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        Arrays.sort(N);

        for (int i = 0; i < num; i++) {
            System.out.println(N[i]);
        }
    }
}

Python

num = int(input())
list = []

for i in range(num):
    list.append(int(input()))

list.sort()

for i in range(num):
    print(list[i])

참고

[Dual-Pivot Quick Sort] 두 개의 피봇으로 퀵 정렬
Dual-Pivot Quicksort Explained and Implemented with Examples in Java