[Baekjoon] 10989번: 수 정렬하기 3

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

문제 설명

들어온 수를 다음과 같이 정렬해서 출력하는 문제입니다.

처음엔 파이썬으로 풀었고 리스트에 입력받고 리스트.sort() 로 정렬한뒤에 for문으로 출력하면 될 간단한 문제인줄 알았으나...

 

자세히 보면 메모리 제한이 8 MB 입니다.

수 정렬하기 2가 메모리 제한이 256MB로 기억하는데 메모리 제한이 32배나 차이가 납니다.

 

일단 확실한건 입력 데이터 N의 갯수 범위가 (1 ≤ N ≤ 10,000,000)인데 이 크기만큼 배열, 리스트를 만들어서 받아낸후 정렬하면 무조건 메모리 초과가 뜨게 됩니다.

 

int형 배열로 단순 계산을 해도 10000000 x 4byte = 38.146973MB 정도가 나옵니다.

제한이 8MB 이기때문에 한참 초과해버립니다.

 

생각보다 조건이 까다롭고 파이썬이라는 언어 자체가 메모리를 많이 먹어서 더 힘들었습니다.

그래서 이 문제를 해결 하는 방법은 계수 정렬(Counting Sort) 을 이용하는 방법입니다.

 

https://www.youtube.com/watch?v=n4kbFRn2z9M 

계수 정렬이 뭔지 모르시겠다면 위 영상을 잠깐 보고 오시면 쉽게 이해하실 수 있습니다.

* 본 글에선 계수 정렬에 대해 자세히 다루지 않으나 나중에 포스팅에서 자세히 다뤄볼 예정입니다.

 

계수 정렬이란 간단히 수를 저장해서 그 배열을 정렬하는게 아닌 수가 들어오면 배열을 하나 만들고 그 해당 인덱스로 이동하여 그 수가 몇번 나왔는지 기록하는 것입니다. 그리고 for문으로 순서대로 출력하면 정렬이 완료되게 됩니다.

 

사실 계수 정렬을 사용해야 한다는 것은 문제에 힌트가 있었는데요.

 

입력 부분에 보시면

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

 

N이 1~10000으로 제한되어 있습니다.

 

즉 이 문제를 풀땐 생각을 조금 바꾸어서 입력 데이터를 모두 저장하는게 아니라

1~10000까지 각각 몇번씩 나왔는지 배열에 기록하고

그 기록한 배열을 순서대로 출력하는 문제가 되겠습니다.

 

 

 

소스코드 & 설명

오늘은 소스코드가 두개입니다.

하나는 파이썬,  하나는 C언어 입니다.

 

#For Python
from sys import stdin
counting = {}

n = int(stdin.readline())
for i in range(n):
    a = int(stdin.readline())
    if not a in counting:
        counting[a] = 1
    else:
        counting[a] += 1
for i in range(1, max(counting)+1):
    if i in counting: #딕셔너리에 있는지 검사한다.
        for j in range(counting[i]):
            print(i)

계수정렬 파이썬 코드입니다. input()이 아닌 readline() 으로 입력을 받습니다.

파이썬의 input 은 효율성이 떨어져서 빨리 입력받으려면(시간 초과를 안당하려면) readline() 으로 보통 받습니다.

이 문제는 input 으로 통과 자체가 안된다는데 메모리 측면에서도 비효율성을 가지는것으로 추측됩니다.

 

코드 효율성을 위해 리스트가 아닌 딕셔너리로 만들었고 딕셔너리는 해시 테이블로 구현된 것이기 때문에 순서가 따로 없습니다.

 

그래서 순서대로 출력하려면 정렬을 하고 출력하는 방법, 아니면 for문을 쭉 돌아서 요소가 있으면 출력하는 방법이 있는데 딕셔너리 정렬을 해버리면 메모리 초과가 떠버립니다.

 

딕셔너리는 요소 검색시 시간복잡도가 $O(1)$인 상수시간을 가지기 때문에 차라리 for문으로 iteration 을 돌면서 요소 검사를 하는게 더 효율적으로 보입니다.

 

//For C
#include <stdio.h>

int main(){
	//Counting Sort
	int n = 0 , k = 0;
	int arr[10001] = {0, }; //0~10000
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		scanf("%d", &k);
		arr[k] += 1;
	}
	
	for (int i = 0; i < 10001; i++){
		for(int j = 0; j < arr[i]; j++){
			printf("%d\n", i);
		}
	}
	
	return 0;
}

위는 C언어로 구현한 계수 정렬 코드입니다.

 

참고로 배열을 10000개가 아니라 10001개만든 이유는

인덱스와 그 출력할 숫자의 순서를 맞춰주기 위해서 입니다.

 

ex) 0번 인덱스는 0이 몇개인지.. 1번 인덱스는 1이 몇개인지..

 

 

C언어는 언어 자체가 메모리 자체를 적게 먹는데 파이썬으로 이 문제를 통과할땐 조금 어려움을 겪었습니다.

 

이 문제를 통과하기 위해선

1. sort()는 최대한 지양한다.
2. 계수 정렬을 이용한다.

가 핵심이 되겠습니다.
잘 유념하셔서 풀의하시면 되겠습니다.

결론적으론 두 코드 모두 잘 통과합니다. 

C언어랑 파이썬이랑 메모리 차이가 거짐 30배가 나는군요..