문제

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

입력

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

출력

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

예제 입력 1

554321

예제 출력 1

12345

접근방법

정수 포인터 선언하고 동적할당해줘서 배열을 만들고 퀵소팅 알고리즘으로 풀어보자.

어려웠던점

시간복잡도에서 걸려서 문제였다. 직접 만든 퀵소팅은 인덱스0을 피봇으로 잡고 재귀를 도는방식인데 한번에 하나씩 바뀌는게 문제였던것 같다. 다른 방법을 찾아보니 트리를 이용한 힙정렬과 병합정렬이라는걸 찾아볼 수 있었고 라이브러리(stdlib.h)에 내장된 퀵소트를 사용하는 법도 찾아볼수있었다. 가장 쉬운 라이브러리 사용으로 해결해보았다.

배운점

라이브러리를 잘 활용하자.qsort(배열, 배열의 요소 개수, sizeof(요소), 비교함수)예) qsort(array, N, sizeof(int), compare)compare(const void *a, const void *b)이 문제에선 int의 배열이였으므로 int요소를 각각 비교하게된다. 매개변수는 void *이므로 형변환을 해줘서 비교할수있게 작성한다. *(int *)a < *(int *)b 이런식으로 void *를 먼저 int 로 형변환한 후 역참조한 값을 비교해서 1, -1, 0값을 도출할 수 있도록 한다.만약 구조체 배열을 비교해서 정렬해야한다면, ((구조체 포인터)a).member 이런식으로 비교할수 있을듯 하다.

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