문제
출처: https://www.acmicpc.net/problem/10989
오답 분석
저는 먼저 파이썬에 내장된 정렬 함수인 sort를 이용해서 풀려고 했습니다. 하지만 저번 2751 수 정렬하기 2 문제와 다르게 메모리 초과가 발생했습니다.
그 이유는 입력되는 정수의 개수 N과 입력되는 정수의 최대 값 n의 차이를 제대로 파악하지 못했으며, 메모리 범위를 고려하지 않아 문제가 발생하였습니다.
아래는 제가 처음 제출한 코드입니다.
이 문제의 핵심은 메모리의 최대값은 8MB인 것과 입력되는 정수의 개수 N의 범위는 (1 ≤ N ≤10,000,000)라는 것입니다.
파이썬에서 정수 값은 기본적으로 4byte 메모리를 할당합니다. 만약 모든 데이터의 입력을 리스트에 저장한다면 4byte * 10,000,000 = 40MB의 메모리가 필요합니다. 이 문제의 핵심을 잘못 파악하여 문제를 푼 것입니다.
저는 위 문제를 계수 정렬이라는 특이한 정렬 방식으로 해결하였습니다.
계수 정렬
계수 정렬은 다음 조건을 만족해야 사용할 수 있는 정렬 알고리즘입니다.
- 모든 데이터가 양의 정수여야 합니다.
- 데이터의 크기 범위가 제한되어 정수 형태로 표현 할 수 있을때 사용 가능 합니다.
- 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않아야 합니다.
2.를 자세하게 설명하면 이 문제에서 입력되는 정수는 10,000보다 작거나 같은 자연수이다. 라는 조건이 있습니다.
이는 데이터의 크기 범위가 10,000으로 제한 된 양의 정수를 의미합니다.
따라서 위 10989 문제는 이 두 조건을 모두 만족하여 계수정렬로 풀 수 있습니다.
계수정렬의 시간 복잡도는 O(N + K) 입니다.
N = 데이터의 개수 (이 문제는 최대 10,000,000)
K = 데이터 중 최대 값(10000)
따라서 계수 정렬의 최대 시간 복잡도는 O(N)이며, 공간 복잡도는 4byte * 10,001 = 40KB = 0.04 MB 첫번째 코드 보다 1/10000로 줄어든 것을 확인할 수 있었습니다.
계수 정렬은 값을 비교하며 순서를 바꾸는 것이 입력되는 양수와 깉은 인덱스를 하나씩 증가시키고 이를 처음부터 출력하는 방식입니다.
for문을 1번만 실행하면 되기에 O(N+K) 가 되는 것 입니다.
(K 가 나오는 이유는 N=2, 두 정수가 0, 999,999인 경우 N은 큰 K값에 의해 무시되어 O표기법으로 표현될 수도 있기 때문입니다.)
계수 정렬을 이용하여 문제를 해결하였습니다.
두 번째 코드 (정답)
python 3 로 제출한 코드는 다음과 같습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import sys
n = int(sys.stdin.readline().rstrip())
a = [0]*(10001)
for i in range(n):
num = int(sys.stdin.readline().rstrip())
a[num] += 1
# 내장 sort함수가 아닌 계수정렬이용하기
#a.sort()
for i in range(10001):
# sys.stdout.write(str(a[i])+"\n")
if a[i] != 0:
for j in range(a[i]):
print(i)
하지만 이 코드를 PyPy3로 제출한 결과 메모리 초과라는 결과가 나와 틀렸습니다.
1
sys.stdout.write(str(a[i])+"\n")
코드를 사용하면 개행 문자를 없애고 파라미터를 위한 메모리 공간도 할당되지 않아서 메모리 문제를 해결할 수 있을 것 같아 코드를 아래와 같이 약간 수정하고 PyPy3 로 제출 해보았습니다.
세 번째 코드 (정답)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import sys
n = int(sys.stdin.readline().rstrip())
a = [0]*(10001)
temp = 0
for i in range(n):
num = int(sys.stdin.readline().rstrip())
a[num] += 1
# 내장 sort함수가 아닌 계수정렬이용하기
#a.sort()
for i in range(10001):
if a[i] != 0:
for j in range(a[i]):
sys.stdout.write(str(i)+"\n")
실행 속도가 3배 가량 향상 하였지만 메모리는 그만큼 4배 더 많이 사용하였습니다. 코드와 언어에 따라 시간과 공간의 trade-off 가 발생하는 것을 확인할 수 있었습니다.
결론
문제의 조건에 맞게 코드를 적절하게 작성하는 것이 전략이 코딩테스트를 통과하는 데에 큰 도움을 준다는 것을 깨달았습니다.