백준 10989 C/C++

www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

바로 전 포스팅이 수 정렬하기 2였습니다.

알아보니 수 정렬하기 3도 있어서 하는김에 비슷할 것 같아서 그냥 수 정렬하기 2에 있는 그대로 제출을 하였습니다.

하지만 제출을 하고 나니 메모리 초과가 떴었습니다. 

메모리 초과...? 한번도 떴었던 적이 없었던 사항인데 뭐지 싶어서 메모리 초과를 검색을 하고 이러한 상황을 겪은 다른 사람들의 글들을 읽어 보았습니다. 

www.acmicpc.net/board/view/21587

글 읽기 - 메모리 초과 문제를 어떻게 해결해야 할까요?

바로 여기서 해답을 알게 되었습니다.

int형의 천만정도이면 40MB정도라는 사실을 알게 되었습니다.

그래서 아 여기서는 10000000을 사용하면 안되겠구나를 깨닫게 되었고 그 이후 풀 수 있는 정렬 방법이 무엇이 있을지 생각을 해보았습니다.

 

그러다 문득 비교해서 정렬을 하는 것이 아닌 그냥 문제상에서는 작은 것을 입력받은 것 부터 출력을 하면 되니까. 10001짜리 배열을 만들어서 거기에 ++을 해서 while문을 돌리는것은 어떨까라는 생각을 하였고

바로 코딩을 하였습니다. 

 

그러자 바로 돌아갔습니다.

아래 코드는 제가 코딩한 코드입니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

int main()
{
	int suList[10001] = { 0, };
	int n; int su;

	scanf("%d", &n);		//수의 개수를 받음.

	for (int i = 0; i < n; i++) {
		scanf("%d", &su);			//수가 10이 들어오면 suList[10]++이 되는 for문이다.
		suList[su]++;
	}

	int count = 1;
	while (1) {
		if (count == 10001) {
			break;
		}

		while (suList[count] != 0) {
			suList[count]--;
			printf("%d\n", count);
		}
		count++;
	}
	
}

저번에 했던 수 정렬하기 2도 배열의 크기를 조절하면 가능할 것 같지만 merge sort를 익힌다는 생각으로 풀었던 문제라서 나름 의미가 있었던 것 같습니다.