[BOJ] 백준 10989번 수 정렬하기 3 풀이

| |
백준 온라인 저지 백준 10989번 - 수 정렬하기 3 C++ 풀이


문제

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


입력

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


출력

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


풀이

단순 정렬 문제임에도 불구하고 제출 수가 10만이 넘어가는 정답률 20퍼짜리 문제이다. 다른 문제들과 뭐가 다른지 자세히 살펴보면 메모리 제한이 8MB임을 알 수 있다. 하지만 받아야하는 수의 개수는 1천만 개이므로 수를 단순히 저장하는 것 만으로 메모리가 초과됨을 예상할 수 있다. 하지만 이것 외에 이 문제의 또 다른 특징이 있는데 바로 모든 수가 10000보다 작다는 것이다. 즉, 메모리 사용량이 지극히 적은 대신 아주 작은 수만 비교하여 정렬한다. 여기서 떠올려야 할 정렬 알고리즘은 바로 카운팅 정렬이다.

입력받은 수를 저장하지 않고, 모든 수마다 몇 번 등장하는지만 체크한다.

이 때, 수는 10000을 넘기지 않으므로 길이가 10000인 배열을 만들면 모든 수 마다 몇 번 등장하는지 체크할 수 있다. 아래 코드를 통해 확인할 수 있다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);

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

   while(N--){
      int n; cin>>n;
      cnt[n]++;
   }

   for(int i=1;i<=10000;i++)
      while(cnt[i]--)
         cout<<i<<'\n';

   return 0;
}
0%