📘[백준-10989] 파이썬 메모리 초과(Python)

파이썬 메모리 초과

[백준-10989: 수 정렬하기3] 문제를 풀다보니 메모리 초과라는 문제가 생겼다.
구글링 해보니, 많은 입력을 전부 배열에 저장하거나, sort() 함수를 사용하면 메모리 초과가 발생할 확률이 높다고 하더라..

기존코드

[기존코드]

import sys

N = int(sys.stdin.readline())

arr = []
for i in range(N):
    num = int(sys.stdin.readline())
    arr.append(num)

arr.sort()

for i in range(N):
    print(arr[i])

기존에 계속 하던 것 처럼 sys.stdin.readline()으로 입력을 받고, 배열 arr에 입력들을 담았다.
그 결과를 sort()를 사용해 정렬을 하고 제출했지만 메모리 초과는 해결이 되지 않았다.

해결

[정답코드]

# (알고리즘 문제풀이에서) 모든 입력을 배열에 저장하면 당연히 메모리 초과 입니다.
# sort()를 사용하면 메모리초과날 확률 높음

import sys

N = int(sys.stdin.readline())

arr = [0 for _ in range(10001)]

for i in range(N):
    num = int(sys.stdin.readline())
    arr[num] += 1

for i in range(len(arr)):
    if arr[i] != 0:
        for j in range(arr[i]):
            print(i)

먼저 적당하게 큰 배열을 직접 선언한다.
그 배열은 전부 0으로 초가화!

그러면 배열이 적당히 크게 0으로 초기화 되고, 입력들을 배열에 저장하는게 아니라 배열의 자릿수에 입력 값들을 저장하는 방식이다.
만약 N=3, input=1,2,3이라고 하면 arr = [0, 1, 1, 1, 0, 0, 0, … , 0]과 같이 되는 것이다.
중복된 값이 들어오면 그 자리에 +=1로 계속 더해준다. -> 나중에 반복 횟수로 사용할 예정임.

아래 반복문에서는 배열의 값이 0이 아니라면 배열의 요소 값(1 이상)만큼 반복을 하며, 그 배열의 인덱스를 출력한다.

참고자료

https://coarmok.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%ACpython-%EB%B0%B1%EC%A4%80-10989%EB%B2%88-%EB%A9%94%EB%AA%A8%EB%A6%AC-%EC%B4%88%EA%B3%BC
https://wikidocs.net/130182