2751: 수 정렬하기2

-Class2 : Silver5

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

2751번: 수 정렬하기 2

 

-결과

 

-코드

#include <stdio.h>
#include <stdlib.h>

int num[1000000];
int compare(const void *a, const void *b)
{
    int num1 = *(int *)a;
    int num2 = *(int *)b;
 
    if (num1 < num2)
        return -1;
    if (num1 > num2)
        return 1;
    return 0;
}
int main()
{
 
    int n;
    scanf("%d", &n);
    for (int a = 0; a < n; a++)
    {
        scanf("%d", &num[a]);
    }
    qsort(num, n, sizeof(int), compare);
    for (int i = 0; i < n; i++)
    {
        printf("%d\n", num[i]);
    }
    return 0;
}

 

-풀이

이 문제는 대략 2~3달 전에 자바로 시도했다가 틀린 문제다. 시간 초과로 틀려서 어떻게 수정해야 하는지 감이 잘 안 잡혔었는데 이번에 c로 풀면서 어떻게 풀어야 되는 건지 알게 되었다.

일단 이전에 풀었을 때와 마찬가지로 정렬을 이용해서 푸는 문제이다.

그리고 그 중에서도 퀵정렬을 쓰는 게 가장 좋다.

늘 코드를 작성할 때는 범위를 잘 확인해야 한다. 이 문제는 수의 개수를 최대 1,000,000이라고 했으므로 num[ 1,000,000]으로 맞춰준다.

compare 함수를 이용해서 num1값이 num2값보다 크면 1을 출력하도록 한다. (작으면 -1을 출력)

그리고 main 함수에서 수를 n번 입력받고, qsort함수를 이용해서 정렬을 하고 출력한다.

 

*qsort함수에 대한 설명

참고: https://dojang.io/mod/page/view.php?id=638 

C 언어 코딩 도장: 73.2 퀵 정렬 함수 사용하기