[알고리즘 문제 풀이][정렬] 백준 10989번 - 수 정렬하기 3

백준 10989번 수 정렬하기3 문제입니다.

(정렬 문제)

 

- 문제 설명: https://www.acmicpc.net/problem/10989

- 문제 풀이:

 

본 문제를 풀 때 중요한 것은 입력 제한을 보고 가능한 정렬 방법을 떠올리는 것입니다.

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

 

본 문제의 메모리 제한은 8MB 입니다. 그런데 들어오는 수의 개수가 10,000,000 개이기 때문에 이걸로 배열을 만든다고 하면 4 byte * 10000000 = 40 MB 가 필요합니다. 그래서 들어오는 수를 정렬하는 방식으로는 풀 수가 없습니다. 대신 들어오는 수가 10000 보다 무조건 작다는 제한이 있기 때문에 이를 이용하여 풀 수 있습니다. 들어오는 수의 범위가 작을 때 사용할 수 있는 정렬 방식은 바로 Counting Sort입니다.

 

- 코드: 

import sys

counting = [0]*10001
t = int(sys.stdin.readline())
for _ in range(t):
	counting[int(sys.stdin.readline())]+=1

for i in range(10001):
        for j in range(counting[i]):
                sys.stdout.write(str(i) + '\n')

본 문제를 풀어보면 python 의 input() 과 print() 를 쓰면 시간초과가 나는 것을 볼 수 있습니다.

print() 만 sys.stdout.write() 함수로 바꿔도 시간 초과를 해결할 수 있으며, 조금 더 시간 단축을 위해 input() 함수도 sys.stdin.readline() 으로 변경한 코드입니다.

 

- 실수 포인트 & 반례:

1. 메모리 초과

대부분의 질문 답변은 메모리 초과의 원인에 대해서 묻고 있습니다.

본 문제에서 메모리 초과의 원인은 2가지가 있습니다.

(1) 카운팅 소트를 하지 않고 배열을 크게 잡는 경우

(2) print 를 일일히 하지 않고 .append() 하거나 문자열들을 합해서 한 번에 출력하는 방식을 쓰는 경우

ex. java의 경우, BufferWriter BufferReader 를 사용해야합니다.

https://www.acmicpc.net/board/view/63901

 

2. 시간 초과

빠른 입출력을 사용하지 않으면 본 문제의 시간 제한에 걸리게 됩니다.

ex. python 의 경우 print() 함수를 쓰면 시간 초과를 받게 되며, sys.stdout.write() 를 써야 통과됩니다.

 

[정리된 QnA 게시글 참고]

https://www.acmicpc.net/board/view/26132

1. 모든 입력을 배열에 저장하면 당연히 메모리 초과입니다. 문제의 메모리 제한은 겨우 8MB입니다. 아무리 작은 자료형으로 저장한다고 해도 short형 (2바이트) 천만 개면 약 20MB로 역시 메모리 초과입니다. 입력을 전부 저장하지 않고 푸는 방법을 생각해 보세요. 힌트는 입력되는 정수의 범위에 있습니다.

2. (C++) endl 쓰지 말고 '\n' 쓰세요. endl은 버퍼를 flush하기 때문에 매우, 매우, 매우 느립니다. 이건 이 문제 뿐만이 아니라 앞으로 푸실 모든 문제에 대해 공통입니다.

3. int a[10000]; 의 원소는 9999까지입니다.

4. 느린 입출력을 써도 시간 초과가 될 수 있습니다. https://www.acmicpc.net/proble... 에서 내가 충분히 빠른 입출력을 쓰고 있는지 확인해 보세요.

5. Pypy를 쓸 경우 print가 아니라 sys.stdout.write를 해야 메모리 초과를 받지 않습니다.

통과는 됐는데 너무 느리다면 다음과 같은 이유가 있습니다.

- 위의 1번의 경우 메모리 보너스가 있는 언어들에는 해당되지 않을 수 있습니다. 하지만 기본적으로 sort는 원소들의 비교를 통해 정렬을 수행하고, O(nlogn)의 시간복잡도를 가집니다. 천만 로그 천만은 2억 3천 정도로 상당히 무겁습니다. 애초에, 이 문제는 그렇게 풀라고 만든 문제가 아닙니다. 이런 식의 풀이를 허용할 거라면 굳이 메모리 제한을 넉넉하게 안 주고 8MB로 빡세게 할 필요가 없죠. 그럼 어떻게 할까요? 힌트는 사실 위에 3번에 있습니다.

- O(nlogn)보다 빠르게 풀 수 있는데도 시간 제한이 3초씩이나 되는 건 바로 입력을 받는 것 자체가 그와 맞먹는 수준의 느린 속도를 자랑하기 때문입니다 (사실 입력량 자체가 O(nlog(최대자릿수))입니다). C++이라면 ios_base::sync_with_stdio(false); 를 하는 것만으로도 엄청난 속도의 향상을 볼 수 있고, Java라면 BufferedReader, Python에서는 sys.stdin.readline이 있습니다 (파이썬은 input()으로는 통과 자체를 못 하는 것으로 알고 있습니다). C 계열의 경우 fread나 mmap을 쓰면 정말 말도 안 되는 속도의 향상을 볼 수 있지만, 이건 해보고 싶은 사람만 해보면 됩니다.