[백준] 2751(수 정렬하기 2) c언어

문제

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

입력

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

출력

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

 

---

 

처음엔 선택정렬 생각하고 제출했는데 시간초과가 떴다.

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

int main(void) {
  int n;
  scanf("%d", &n);

  int temp = 0;

  int *arr;
  arr = (malloc)(n * sizeof(int));

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

  for(int i=0; i<n-1; i++) {
    for(int j=i+1; j<n; j++) {
      if(arr[i] > arr[j]) {
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] =temp;
      }
    }

  }

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

  free(arr);
}

 

검색해보니, 어떤 정렬을 써도 시간 초과가 나기 때문에 c언어에서는 qsort() 함수를 써야 한다고 한다. 

전에 qsort() 사용해서 푼 문제가 있어서 > https://h-factory.tistory.com/624

똑같이 쓰려고 했는데, 위 문제는 배열 2개를 사용했을 때라 사용법이 약간 다르긴 했다.

 

https://twpower.github.io/56-qsort-in-c > 배열 하나를 오름차순으로 정렬할 때 qsort() 함수 사용법!!

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

typedef struct {
  int x, y;
} Point;

int compare(const void *a, const void *b){
    Point p1 = *(Point*)a, p2 = *(Point*)b;
    if (p1.x < p2.x)
        return -1;
    else if (p1.x > p2.x)
        return 1;
    else {
        if (p1.y < p2.y)
            return -1;
        else if (p1.y > p2.y)
            return 1;
        return 0;
    }
}

int main(void) {
  int n;
  scanf("%d", &n);

  int *arr;
  arr = (malloc)(n * sizeof(int));

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

  qsort(arr, n, sizeof(int), compare);
  
  for(int i=0; i<n; i++) {
    printf("%d\n", arr[i]);
  }

  free(arr);
}

 

> qsort() 함수에 대해 좀 더 정확히 알아야할 것 같다...