[C 언어] 백준 10989. 수 정렬하기 3

---

10989. 수 정렬하기 3 (누르면 해당 문제로 이동)

수의 범위가 작다면 카운팅 정렬을 사용하여 더욱 빠르게 정렬할 수 있습니다.

 

제약사항)

시간 : 3 초

메모리 : 8 MB

 

* 시간 제한 안내 (아래 적혀있지 않은 시간 제한은 언어 도움말에 적혀있는 기준을 따른다.)

   Java : 3초 / Java(OpenJDK) : 3초 / Java 11 : 3초 / Kotlin(JVM) : 3초

* 메모리 제한 안내 (아래 적혀있지 않은 메모리 제한은 언어 도움말에 적혀있는 기준을 따른다.)

   Java : 512MB / Java(OpenJDK) : 512MB / Java 11 : 512MB / Kotlin(JVM) : 512MB

 

문제)

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

 

입력)

첫째 줄에 수의 개수 N(1<=N<=1,000,000)이 주어진다.

둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000 보다 작거나 같은 자연수이다.

 

출력)

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

 

입출력 예제

입력	출력
10 5 2 3 1 4 2 3 5 1 7	1 1 2 2 3 3 4 5 5 7

 

---

 

풀이 순서)

카운팅정렬에 관해 참고한 페이지입니다.

위 페이지의 내용대로 하나씩 구현해보니, 메모리 초과 및 시간 초과로 실패했습니다.

 

1. 입력 숫자를 num[] (배열) 로 입력받고, cnt[]를 계산한 후 누적 카운팅을 계산한다.

2. 누적 카운팅에 따른 결과를 배열에 저장하고 출력한다.

 

위 과정은 실패했을 때 구현했던 방법입니다.

 

따라서, 배열은 카운팅(cnt[]) 배열만 남기고 나머지는 간단한 변수 혹은 출력으로 대체하도록 바꾸었습니다.

 

1. 숫자를 변수로 입력받아 해당 인덱스를 찾아 cnt[숫자] 값을 증가시킵니다.

2. cnt 값이 0이 아닐 때, cnt 값만큼 인덱스 값을 출력합니다.

 

위 과정에 따라 구현하니 시간, 메모리 초과 없이 성공할 수 있었습니다.

 

---

 

소스코드 및 결과 (C)

#include <stdio.h>

#define size 10001

int cnt[size] = { 0, };

int main() {
	int N, num;

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

	for (int i = 0; i <= size; i++) {
		if (cnt[i] == 0)
			continue;
		
		for (int j = 0; j < cnt[i]; j++)
			printf("%d\n", i);
	}

	return 0;
}

 

메모리 : 1152 KB

시간 : 2372 ms

코드길이 : 323 B

 

 

---