[백준] 10989번: 수 정렬하기3

문제 링크 : https://www.acmicpc.net/problem/10989

 

문제 풀이

Counting sort로 풀었다.

계수 정렬 게시글 https://manzoo.tistory.com/57 의 소스 코드로 제출하였더니 메모리 초과가 났다.

문제를 다시 자세히 보니 메모리 제한이 8MB로 걸려져 있었다.

하지만 데이터 값은 10000을 넘지 않는다는 조건이 있었다.

그래서 입력 데이터 수 만큼 배열을 할당하지 않고 카운트 배열만 10001만큼 할당을 받았다.

입력받는 대로 바로 count 배열에 저장한 후, 앞에서부터 개수만큼 출력을 했다.

 

하지만 그대로 제출하니 시간초과가 떴다.

cin → scanf

cout → printf 로 변경하니 시간초과가 뜨지 않았다.

 

소스코드

/*
 * 백준 10989번: 수 정렬하기 3
 */

#include <iostream>

using namespace std;

#define MAX 10001

int main() {
	int N;
	scanf("%d", &N);

	int count[MAX]{ 0, };

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


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

	return 0;
}