백준 2751 번 문제 풀이 C C언어 :수 정렬하기 2

#76. 백준 2751번 문제 풀이: 수 정렬하기 2

N개의 수가 주어졌을 때, 오름차순으로 정렬하는 프로그램을 작성하시오. 입력: 첫줄에 수의 개수(1 ≤ N ≤ 1,000,000). 둘째 줄부터 한 줄에 하나씩 N개의 수가 주어진다. 이 수는 절댓값은 1,000,000보다 작거나 같은 정수이며 중복되지 않는다. 출력: N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력.

입력/출력

--입력--
5
5
4
3
2
1
--출력--
1
2
3
4
5

문제풀이+해설

이 문제는 단순히 소팅을 하는 것 처럼 보인다. 
하지만 대부분 시간초과라는 결과를 맞게 될 것이다.

한 줄에 하나씩 최대 1,000,000개의 입력 처리가 시간내에 가능해야 하기 때문에 입력처리 속도를 줄이는 방법으로 코딩하는게 이번 문제의 의도이다.
프로그래밍 언어마다 입출력 방식은 여러가지가 있다.

소팅은 각 언어에서 기본으로 제공하는 소팅함수들을 사용

파이썬: 
 일반적으로 input(),속도를 위해 getline() 함수를 사용해야 한다.
C/C++ 언어:
 이번 문제에 한해서 기본 입력함수 scanf 나 cin 으로도 충분히 빠르기 때문에 그냥 사용하면 된다.

code sol.

코드편집/실행

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

// qsort 함수에 사용하기 위해 비교함수를 만든다.
int compare(const void *a, const void *b) {
  int na = *(int *)a;
  int nb = *(int *)b;  
  if(na < nb) return -1;
  if(na > nb) return 1;
  return 0;
}

int main() {
  int i;
  int N; //수의 개수 변수
  int ns[1000000]; // 수를 입력 받을 배열
  scanf("%d", &N); // 수의 개수 입력받음.
  for(i = 0; i< N; i++) { // 주어진 N개 만큼 입력 받음
    scanf("%d", &ns[i]); // 숫자를 입력받아 배열에 넣음.
  }
  qsort(ns, N, sizeof(int), compare); // qsort 로 배열 소팅
  for(i = 0; i < N; i++) {
    printf("%d\n", ns[i]); // 한줄에 하나씩 출력
  }
  return 0;
}