[코딩 테스트] 문제에서 시간 초과, 메모리 초과 예상하기 #python

문제

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

 

N개의 수가 주어지고 범위는 [1,10_000_000]이다.

보통 1초에 1억번의 연산을 한다는 가정을 해서 시간 초과 여부를 계산할 수 있다.

 

해당 문제의 시간 제한은 5초이며,

연산에 O(N^2)만큼 걸리면 10,000,000 * 10,000,000번의 연산을 해야하고 1,000,000 * (1억번의 연산) = 1,000,000초가 걸려 시간 초과다.

O(NlogN)의 경우 대략 23*10,000,000으로 2.3초 정도 걸려 시간 제한 내에 통과한다.

 

물론 파이썬에 주어지는 시간, 메모리 보너스가 있고 이를 고려해도 마찬가지다.

(보너스 적용 시 시간 제한: 17초, 메모리 제한: 48MB)

https://help.acmicpc.net/language/info

 

풀이

이 문제를 봤을 때 2가지 풀이법이 생각났다.

 

1. 하나는 모든 수를 answer 배열에 받고 sort()로 정렬한 후 '\n'.join(answer) 해주는 것이다. 파이썬의 sort()는 timsort로 O(NlogN)의 시간 복잡도를 가진다.

 

(풀이 1-1) answer에 들어있는 값이 int라서 str로 변환해주어야 했다. 

answer = []
for _ in range(N):
  answer.append(int(input()))
answer.sort()

print('\n'.join(list(map(str, answer))))

 

(풀이 1-2) 위에서 str 변환 연산과 이를 담는 배열까지 시간과 메모리 둘다 비효율적이다. answer배열을 순회하면서 매번 print 해주는 것을 생각했다.

answer = []
for _ in range(N):
  answer.append(int(input()))
answer.sort()

for x in answer:
  print(x)

 

다만, 위 두 풀이 모두 메모리 초과가 예상됐고 그대로 발생했다.

메모리 제한은 8MB가 주어졌는데 (파이썬 보너스 고려 시 48MB) N개가 최대 10,000,000개이다.

풀이 1-1은 최악의 경우 10,000,000개의 str형, 풀이 1-2는 10,000,000개의 int형을 담을 수 있어야 했다. 

 

(str의 경우) C언어에서 str형의 크기는 포인터의 크기로 볼 수 있고 보통의 경우 포인터는 8byte로 80,000,000byte = 80,000KB = 80MB여서 통과할 수 없어 보였다.

 

(int의 경우) int형의 크기는 보통의 C언어 기준인 4byte로 계산해보니 40,000,000byte = 40,000KB = 40MB였다.

48MB 이하지만 파이썬에서 int형의 크기는 C언어에서보다 클 거라 예상되었다.

 

더 찾아보니 파이썬의 int형은 무려 28바이트, str형은 54바이트라는 것이다.

그래서 이 풀이법으로는 메모리 초과를 피할 수 없다.

 

2.

(풀이 2) N개로 주어지는 수 각각이 전부 10,000보다 작거나 같은 자연수였기 때문에 10,000개의 0을 담을 수 있는 배열을 만들어 각각의 인덱스 값이 해당 숫자의 출현 횟수를 의미하도록 해주는 방법이다.

 

10,000개의 int형을 담는 배열은 28byte * 10,000 = 280,000byte = 280KB = 0.28MB로 메모리 초과의 걱정은 없다.

import sys
input = sys.stdin.readline

N = int(input())

numbers = [0 for _ in range(10001)]
for _ in range(N):
  numbers[int(input())] += 1

for i in range(1,10001):
  n = numbers[i]
  while n > 0:
    print(i)
    n -= 1

 

위 메모리 계산법은 코딩 테스트 문제를 풀기 전에 메모리 초과 여부를 판단하기에는 유용하다고 생각한다.

참고 링크

백준

[자주 틀리는 요인] https://www.acmicpc.net/blog/view/70

[BOJ 작동 원리] https://www.acmicpc.net/blog/view/55

[BOJ Help] https://help.acmicpc.net/language/info

python timsort

[파이썬 시간복잡도] https://wiki.python.org/moin/TimeComplexity

[파이썬 sort] https://docs.python.org/3/howto/sorting.html