1. 문제
https://www.acmicpc.net/problem/10989
2. 문제 해석
한줄로 구분되는 숫자를 입력 받은 후에 받은 숫자들을 정렬한 후 다시 한줄씩 출력하는 문제다. 입력 데이터의 개수는 1 <= N <= 10,000,000이다. 시간제한은 5초, 메모리 제한은 8MB이다.
3. 메모리초과
import sys
input = sys.stdin.readline
N = int(input())
numbers = []
for _ in range(N):
numbers.append(int(input()))
numbers.sort()
for number in numbers:
print(number)데이터의 크기가 10의 7제곱이고 시간이 5초라 파이썬 내장함수 sort()를 그대로 사용하면 되겠다고 생각하고 접근하였다. 채점 결과 메모리초과가 났다.
4. 메모리초과 발생하는 경우
스택 오버플로우
한계 이상의 메모리를 사용하면 메모리 초과가 발생한다. 대부분의 경우에는 재귀함수를 너무 많이 호출하는 경우이다. 함수는 호출 될 때마다 스택 메모리에 쌓이게 되고 스택 메모리 한계 이상으로 함수 프레임이 쌓으려는 경우에 메모리초과가 난다. 이를 스택 오버플로우라고 한다. 하지만 이번에는 내가 재귀함수를 사용하지 않았기 때문에 스택 오버플로우 문제는 아니었다.
한계 이상의 객체 생성
https://dibrary.tistory.com/43
메모리를 측정할 방법을 알아보기 위해 서핑을 하다가 위의 글을 알게 되었다.
객체가 얼마만큼의 메모리를 사용하는지를 알려준다. 코드는 다음과 같다.
import sys
# 리스트를 이용한 객체 생성
arr1 = [x for x in range(1,1000000)]
print("리스트 메모리:",sys.getsizeof(arr1))
# 제너레이터를 이용한 객체 생성
arr2 = (k for k in range(1,1000000))
print("제너리이터 메모리:", sys.getsizeof(arr2))위의 코드를 토대로 메모리를 측정해보니 다음과 같았다.
1부터 100만까지의 데이터를 담는 객체를 리스트와 제너레이터로 생성할 때 리스트는 제너레이터보다 10000배의 규모로 메모리를 사용한다.
5. 내 코드의 문제 분석
문제의 데이터 입력 크기는 최대 1000만이고 메모리 제한은 8MB이다. 내 코드는 리스트를 사용하고 데이터가 10개일 때 리스트만의 메모리 사용량은 다음과 같다.
데이터가 10개일 때 136 바이트를 소모한다. 데이터의 크기가 1000만이 되면 136 * 1000만이 되어 1296MB가 되고 이는 약 1GB가 된다.
6. 해결책 방법1: 제너레이터 사용[각하]
처음에 제너레이터를 사용하려고 했다. 하지만 제너레이터는 데이터를 느슨하게 처리할 뿐 결국 모든 데이터를 처리해야하기 때문에 해당 문제에서는 적합하지 않다는 생각이 들어 아이디어 단계에서 각하했다.
7. 해결책 방법2: 인덱스 사용[인용]
문제가 요구하는 것은 입력 데이터들을 순서대로 정렬해서 출력하는 것이다. 그렇다면 데이터를 모두 받기보다는 입력 데이터의 범위 내에 해당하는 배열을 생성해서 데이터의 수만큼 키값을 올리고 순서대로 출력하면 되지 않을까 생각했다. 그래서 바로 구현하기로 했다.
import sys
input = sys.stdin.readline
N = int(input())
numbers = [0]*100001
# 데이터를 받는 대신에 인덱스로 개수 처리
for i in range(N):
number = int(input())
numbers[number] += 1
# 인덱스를 토대로 숫자를 순서대로 출력
for i in range(1, 10001):
if numbers[i] > 0:
for k in range(numbers[i]):
print(i)
마지막까지 긴장의 끝을 놓치지 말아야했다. range()를 사용할 때 두번째 매개변수는 순회범위에서 제외되는데 10001이 아닌 10000으로 설정해서 틀렸다.
8. 회고
알고리즘 문제를 풀 때 주로 시간초과에 대해서만 고려했는데 이번 문제를 계기로 메모리 초과에 대해서도 생각을 해볼 시간을 가지게 되었다. 메모리 측정하는 방법에 대해서도 배우게 되었고 데이터를 모두 받는 방법 외에 데이터를 받는 대신에 표기로 대체할 수 있는 방법도 배우게 되었다.