[C언어] 백준 2750번 수 정렬하기

 

링크

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

2750번: 수 정렬하기

 

 

 

 

 

문제

---

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

 

 

 

입력

---

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

 

 

 

출력

---

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

 

 

 

예제 입력1

---

5

5

2

3

4

1

 

예제 출력1

---

1

2

3

4

5

 

 

 

아이디어 스케치

---

- 이 문제는 단순히 for문과 조건문을 이용하는 버블 정렬을 이용해도 시간 초과가 발생하지 않는다.
- c언어 stdlib 헤더파일에 있는 qsort(퀵정렬)을 이용 하면 더 적은 시간복잡도로 문제를 해결할 수 있다.

 

 

 

코드 분할 설명

---

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

qsort(arr, N, sizeof(int), compare);		//퀵 정렬

 

- N만큼의 숫자를 입력 받아 배열에 저장한 후 퀵 정렬을 수행하는 코드이다.
- 퀵정렬의 인자로는 ([정렬 할 배열],[배열 요소의 갯수],[배열 요소의 개별 크기],[비교함수])이다.
- 만약 char형이면 sizeof(char)을 입력하면 된다.

 

 

 

 

int compare(const void* first, const void* second)
{
	int a = *(const int*)first;
	int b = *(const int*)second;

	if (a > b)
		return 1;			//오름 차순 정렬
	else if (a < b)
		return -1;
	else
		return 0;
}

 

- 퀵 정렬에서 사용하는 비교 함수이다.
- 함수 전달 인자로는 const void* 형으로 받는다.
- 배열의 변수형은 int형이므로 (const int)형으로 전달 인자를 형변환 한다.
- return이 1인 경우에 swap을 하고, 우리는 오름차순으로 정렬 해야 하므로 first>second 일 때 return 1을 해줌으로써 오름차순 정렬을 한다.

 

 

 

 

전체 코드

---

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

int compare(const void* first, const void* second)
{
	int a = *(const int*)first;
	int b = *(const int*)second;

	if (a > b)
		return 1;			//오름 차순 정렬
	else if (a < b)
		return -1;
	else
		return 0;
}

int main()
{
	int arr[1001];
	int N;

	scanf("%d", &N);

	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]);

	return 0;
}

 

 

 

 

 

 

제출 결과

---