[백준] 10989번 : 수 정렬하기 3

문제

 

---

풀이

 

이 문제 굉장히 힘들었다. 문제 힌트에 counting sort를 사용하라고 써있어서 정석적인 counting sort로 구현했다. counting sort(계수 정렬)이 어떤 것인지 설명하는 곳은 굉장히 많으므로 생략하도록 하겠다. 아무튼 계수 정렬을 구현하려면 배열이 3개 필요하다 정렬 전 배열, 배열의 값의 누적합을 저장한 배열, 정렬 후 배열. 열심히 구현하고 채점을 돌린 나는 메모리 초과를 맞이했다. N크기의 배열을 동적할당하는 과정에서 메모리 초과가 발생한 것일까? 그래서 처음부터 max만큼의 고정 배열을 선언했다. 또 메모리 초과였다. 찾아보니 정렬 전 배열과 정렬 후 배열을 만들면 안된다고 한다. 정렬 전 배열조차 저장하지 말라니? 아무래도 이 문제는 내가 생각한 계수 정렬이 아니었다.

 

정말 정렬 결과만 출력하는 거라면? 모든 수는 10,000 이하라고 했으니, 해당 크기의 배열인 count_arr을 선언했다. 그리고 input이 들어올 때마다 value에 맞춰 count_arr에 값을 채웠다. 만약 위 예제와 같은 경우였다면

이런 배열이 완성됐을 것이다. 그리고 난 count_arr을 돌며 1을 2번, 2를 2번, 3을 2번, 4를 1번...출력하는 식으로 정렬했다. 원래 계수 정렬은 stable sort이다. 근데 이렇게 하면 stable이고 unstable이고 따질 것도 없이 기존 배열이 남지 않았으니 그냥 정말 출력만 한 꼴이다.

 

이렇게 하고 채점을 돌리니 시간 초과가 나왔다. 메모리 초과가 아닌게 어딘가 싶어 cin.tie(NULL)과 sync_with_stdio(false)를 추가했다. 맞았다고 나왔다. 여러모로 당황스러웠으나 이런식으로도 할 수 있다는 것을 깨달았다.

---

소스코드

 

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N, i, j, key, count_arr[10001], max = 0;
	for (i = 1; i < 10001; i++) //자연수라길래 0은 쓸 일 없겠다 싶어서 1부터 함.
		count_arr[i] = 0;

	cin >> N;
	for (i = 0; i < N; i++) {
		cin >> key;
		count_arr[key]++;
		if (key > max)
			max = key;
	}
	for (i = 1; i < max + 1; i++) {
		for (j = 0; j < count_arr[i]; j++)
			cout << i << '\n';
	}
}