(c++)백준 10989번: 수 정렬하기 3

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

10989번: 수 정렬하기 3

[풀이]

처음에 C++ STL의 sort함수를 이용하여 풀려고 하였으나, 메모리 초과가 떴다. 

그래서 원소의 개수가 10001인 배열 Num[]을 만들어 입력 받는 수 x에 대해 Num[x]의 수를 +1 하여 해당 수가 몇 번 들어왔는지 기록한 뒤, Num[1]~Num[10000]까지 0보다 큰 값이 있는 index를 값만큼 출력하는 프로그램을 짰다.

이 방법을 쓸 때 cin, cout을 썼더니 시간초과가 떴다. cin과 cout이 scanf와 printf보다 많이 느리긴 하지만 시간초과에 영향을 주는 것은 이번이 처음이라 당황스러웠다.

최종적으로 scanf와 printf를 쓰니 통과하였다. 

 

#include <iostream>
#include <cstdio>//scanf, printf
using namespace std;

int N;
int Num[10001];//각 숫자가 몇개 들어왔는지 저장

void input() {
	int n;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &n);
		Num[n]++;
	}
}

void solution() {
	input();
	int cnt = 0;//cnt가 N이 되면 끝내기
	for (int i = 1; i <= 10000; i++) {
		if (Num[i] > 0) {
			for (int j = 0; j < Num[i]; j++) {
				printf("%d\n", i);
				cnt++;
			}
		}
		if (cnt == N)
			return;
	}
}

int main() {
	solution();
	return 0;
}