[Baekjoon Online Judge] 백준 2751번 수 정렬하기 2(C)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 2751번 수 정렬하기 2

(C)

(글쓴날 : 2020.04.02)

 

---

* Baekjoon Online Judge, 백준 2751번 문제 C 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 2751번 수 정렬하기 2

---

1) 문제

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

2751번: 수 정렬하기 2

---

2) 풀이 과정

중복되지 않는 수들이 주어질 때, 정렬해서 출력하는 문제입니다.

시간 복잡도가 O(nlogn)인 정렬 알고리즘을 사용해 주시면 됩니다.

 

저의 경우, 언어에 내장되어 있는 정렬 함수를 사용하기보단 C언어로 직접 정렬 알고리즘을 코딩해 보았습니다.

이 문제는 시간 복잡도가 O(nlogn)인 정렬 알고리즘을 적용하면 되므로, 병합 정렬과 퀵 정렬의 선택지가 있지만 퀵 정렬의 경우 최악의 경우에 시간 복잡도가 O(n²)이 될 수 있어 병합 정렬을 이용해 문제를 해결했습니다.

---

3) 코드

 

* C 코드

#include <stdio.h>
#include <stdlib.h>
 
void merge(int *arr, int p, int q, int r) {
    int i = p;
    int j = q + 1;
    int t = 0;
    int *temp = (int *)malloc(sizeof(int) * (r-p+1));
 
    while (i <= q && j <= r) {
        if (arr[i] <= arr[j])
            temp[t++] = arr[i++];
        else
            temp[t++] = arr[j++];
    }
    while (i <= q)
        temp[t++] = arr[i++];
    while (j <= r)
        temp[t++] = arr[j++];
    i = p;
    t = 0;
    while (i <= r)
        arr[i++] = temp[t++];
 
    free(temp);
}
 
void mergeSort(int *arr, int p, int r) {
    if (p < r) {
    int q = (p + r) / 2;
        mergeSort(arr, p, q);
        mergeSort(arr, q + 1, r);
        merge(arr, p, q, r);
    }
}
 
int main() {
    int N = 0;
 
    scanf("%d", &N);
    int *arr = (int *)malloc(sizeof(int) * N);
    for (int i = 0; i < N; i++)
        scanf("%d", &arr[i]);
 
    mergeSort(arr, 0, N - 1);
 
    for (int i = 0; i < N; i++)
        printf("%d\n", arr[i]);
 
    free(arr);
    return 0;
}

---