• 문제

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

• 입력

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

• 출력

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

• 예제 입력 1
  10
  5
  2
  3
  1
  4
  2
  3
  5
  1
  7

• 예제 출력 1
  1
  1
  2
  2
  3
  3
  4
  5
  5
  7

해결 전략

  이런 귀여운 문제를 무슨 해결 전략이랍시고 포스팅을 하느냐고 생각할 수 있을 정도의 쉬운 문제이다. 하지만, 본인은 학부 알고리즘 수업 석차 2등을 했음에도 이 문제를 최초 시도에서 틀렸다(부끄럽다). 틀렸던 이유는 메모리 제한을 확인하지 않아서인데, 당연히 256MB 정도로 생각하고 풀었던 것이다.

  제한을 보니 8MB였다. 엥? 정수가 10,000,000개인데, 이를 char로 넣어도 10MB인데 어떻게 8MB 내로 해결하지? 순간 의아했다.

  문제를 잘 읽어보았다. 입력받는 수가 자연수이고, 만까지밖에 안된단다.

아하!

  약간 장난처럼 느껴질수도 있는 문제였다. 틀린 사람이 뭔 평가를 하리. 반성하고 바로 해결에 들어갔다. 이 문제를 굳이 분류하자면, 해슁(?) 연습이라고 볼 수 있으려나? 혹여나 본 문제를 해결하지 못하고 고민해서 본 글에 들어온 분이라면, 아래의 문구를 통해 바로 해결 아이디어를 얻을 수 있을 것이다.

입력받는 수가 만까지밖에 안된다고..? 그렇다면,, 이 문제는 비둘기집 원리를 이용하면 되겠네?

  모두 간단한 아이디어가 번뜩일 것이다. 크기 10,000의 배열을 만들어라. 더 이상의 설명은 생략한다.

  (틀려놓고 잘난체하는 것 같아 부끄럽다.. 어서 코드를 첨부하고 도망가도록 하겠다.)

  (한편, 이러한 Idea가 Insight가 되어 간단하게 해결할 수 있는 정렬 PS 문제들이 꽤 많다. 일반적으로 정렬 문제는 난이도가 높지 않은데, 위와 같이 수의 개수가 값의 범위보다 큰 경우 외에도, Topological Sorting 관련 문제도 이러한 아이디어를 토대로 보다 더 쉽게 해결할 수 있는 문제들이 많이 있다. 대표적으로 "백준 1181번 - 단어 정렬", "백준 10814번 - 나이순 정렬" 문제가 있다.)

오늘의 교훈 : 메모리 제한이 터무니없이 작은 경우엔 '함정 문제가 아닐까?'라는 생각을 해보는 습관을 가지자!

#include <iostream>
// BOJ - 10989 Sorting 3
using namespace std;

int num[10001];

int main(void) {
	int n, k;

	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> k;
		num[k]++;
	}

	for (int i = 1; i < 10001; i++) {
		if (num[i] > 0) 
			for (int j = 0; j < num[i]; j++) cout << i << '\n';
	}

	return 0;
}