[백준BOJ] #10989 수 정렬하기 3(C++)

수 정렬하기 3 성공언어 제한

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

5 초 (하단 참고)

8 MB (하단 참고)

295962

70310

53775

23.760%

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

문제

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

 

입력

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

출력

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

 

 

접근방식 

N개의 수를 오름차순 정렬하는 문제이다. 알고리즘 헤더의 sort 함수를 써야하나 생각했지만 메모리 제한이 8MB이다. 

최대 10^7 개의 숫자가 입력되고, 수들은 1<=K<=10^4 로 제한된다. 

 

sort()함수를 과감히 버리고, 이중 for문으로 해결해보려 했지만 for문은 O(n)의 시간복잡도를 갖기 때문에 마찬가지로 시간초과로 실패한다. 

 

→ 계수정렬  

K가 나올 수 있는 크기 +1 로 배열을 미리 만든 후, 해당 값이 몇 번 입력됐는지 count 해준다. 

오름차순으로 출력하는 문제이기 때문에 가능한 접근 방식이다.  내림차순이라면? 거꾸로 count 만큼 해당 수를 출력하면 된다. 

 

※ 빠른 입출력을 잊지 말 것!!

ios::sync_with_stdio(false);
cin.tie(NULL);

 

 

정답코드 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N, idx;
	int cnt[10001] = {};
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cin >> idx;
		cnt[idx] += 1;
	}

	for (int i = 1; i <= 10000; i++)
	{
		for (int j = 1; j <= cnt[i]; j++)
		{
			cout << i << "\n";
		}
	}
}