백준 링크 : https://www.acmicpc.net/problem/10989

문제 개요

N개의 수가 주어졌을 때 오름차순으로 정렬하는 문제이다.

아이디어

• 수의 개수를 저장하는 카운팅 배열을 선언하고 출력 때 이를 활용한다.
  • 입력에 대응되는 배열의 인덱스에 접근해서 값을 1씩 증가시킨다.
  • 출력 과정에서 배열의 값만큼 반복문을 통해 결과를 출력한다.

주의사항

• 오름차순 정렬을 보고, sort함수를 떠올렸을텐데, 이 방법으로 하면 실패처리가 된다.
  • sort함수를 사용하기 위해서는 모든 값을 메모리에 저장해야 하는데, 메모리 제한이 겨우 8MB밖에 없다는 점을 보고 이 방법이 불가능하다는 것을 인지해야 한다.

코드

// 아래의 코드는 dev c++환경에서 동작됩니다.
// visual studio에서는 bit/stdc++.h가 기본적으로 없기 때문에
// 정삭적인 작동이 되지 않을 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

int n, counting[10004], temp;
int main()
{
  ios::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for(int i = 0; i < n; i++)
	{
		cin >> temp;
		counting[temp]++;
	}
	
	for(int i = 0; i < 10004; i++)
	{
		while(counting[i]--) cout << i << "\\n";
	}
  return 0;
}

후기

난이도에 비해 정답률이 상당히 낮다. 많은 사람들이 메모리 제한을 간과하고 알고리즘을 구현했던 것 같다. 평소에 많이 데여서 그런지, 나는 메모리 조건을 보고 sort함수의 생각을 과감히 버렸는데, 그것이 정답에 가까운 행동이었던 것 같다.

역시 코드를 치는 것 만큼 중요한 게 문제를 읽고 조건을 따져보는 것이다.