C 백준 10989 수 정렬하기 3 (정렬)

 

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

---

문제

1. 수 N을 입력받음 (1 <= N <= 10000000)
2. 카운팅 정렬 사용
3. 오름차순

---

 

카운팅 정렬: 계수 정렬, 받은 숫자와 같은 자리의 배열 안의 수를 증가시킨 후 출력 시 배열 자리의 숫자를 안에 들어있는 숫자만큼 출력.

 

 

초기 코드

#include <stdio.h>

int main(void) {
	int N, M, max = 0;
	int num[10000000] = { 0, };

	scanf_s("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf_s("%d", &M);
		num[M - 1] += 1;
		if (max < M) {
			max = M;
		}
	}

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

	return 0;
}

 

최대 10000000개의 수를 받는 거였다...
받는 숫자의 최대는 10000...

최종 코드

#include <stdio.h>

int main(void) {
	int N, M, max = 0;
	int num[10000] = { 0, };

	scanf_s("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf_s("%d", &M);
		num[M - 1] += 1;
		if (max < M) {
			max = M;
		}
	}

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

	return 0;
}

 

num[M - 1] += 1; 부분에서 num[-1]을 가리킬 수 있다고 오류가 뜨긴 하는데 N은 최소 1이니까 문제가 없을 것 같아 놔뒀다.

 

채점 시간이 엄청 오래 걸렸다.