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

2026-03-09

BOJ

C

/

BOJ

문제#

https://www.acmicpc.net/problem/2751

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

입력#

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

출력#

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

풀이#

이 문제는 입력 크기가 최대 1,000,000이므로, 버블 정렬이나 선택 정렬처럼

O(N^2)

이 걸리는 정렬은 사용할 수 없습니다.

보통은

O(N \log N)

정도의 정렬 알고리즘을 사용해야 합니다.

이 문제는 두 가지 방식으로 풀 수 있습니다.

1. 병합 정렬로 푸는 방법#

가장 일반적인 방법입니다.
표준 라이브러리 정렬 함수 없이도 직접 구현할 수 있고, 시간복잡도는

O(N \log N)

입니다.

입력 값의 범위와 상관없이 사용할 수 있어서, 일반적인 정렬 문제 풀이로 적합합니다.

2. 등장 여부 배열로 푸는 방법#

이 문제는 입력되는 수의 범위가

-1{,}000{,}000 \sim 1{,}000{,}000

으로 제한되어 있고, 수가 중복되지 않는다는 조건이 있습니다.

따라서 각 수가 등장했는지를 배열에 기록한 뒤, 작은 값부터 순서대로 출력하면 정렬 결과를 얻을 수 있습니다.

이 방법의 시간복잡도는

O(N + K)

이고, 여기서

K = 2{,}000{,}001

은 가능한 정수 범위의 개수입니다.

즉, 이 문제에서는 병합 정렬보다도 더 단순하게 해결할 수 있습니다.

코드#

코드 1. 병합 정렬#

1
#include <stdio.h>
2

3
#define MAX 1000000
4

5
int arr[MAX];
6
int temp[MAX];
7

8
void merge_sort(int left, int right) {
9
    if (left >= right) return;
10

11
    int mid = (left + right) / 2;
12
    merge_sort(left, mid);
13
    merge_sort(mid + 1, right);
14

15
    int i = left;
16
    int j = mid + 1;
17
    int k = left;
18

19
    while (i <= mid && j <= right) {
20
        if (arr[i] < arr[j]) {
21
            temp[k++] = arr[i++];
22
        } else {
23
            temp[k++] = arr[j++];
24
        }
25
    }
26

27
    while (i <= mid) temp[k++] = arr[i++];
28
    while (j <= right) temp[k++] = arr[j++];
29

30
    for (int x = left; x <= right; x++) {
31
        arr[x] = temp[x];
32
    }
33
}
34

35
int main(void) {
36
    int n;
37
    scanf("%d", &n);
38

39
    for (int i = 0; i < n; i++) {
40
        scanf("%d", &arr[i]);
41
    }
42

43
    merge_sort(0, n - 1);
44

45
    for (int i = 0; i < n; i++) {
46
        printf("%d\n", arr[i]);
47
    }
48

49
    return 0;
50
}

코드 2. 등장 여부 배열#

1
#include <stdio.h>
2

3
#define OFFSET 1000000
4
#define SIZE 2000001
5

6
int exist[SIZE];
7

8
int main(void) {
9
    int n, x;
10
    scanf("%d", &n);
11

12
    for (int i = 0; i < n; i++) {
13
        scanf("%d", &x);
14
        exist[x + OFFSET] = 1;
15
    }
16

17
    for (int i = 0; i < SIZE; i++) {
18
        if (exist[i]) {
19
            printf("%d\n", i - OFFSET);
20
        }
21
    }
22

23
    return 0;
24
}