코드

메모리 초과

# 메모리 초과
n = int(input())
nums = []

for _ in range(n):
    nums.append(int(input()))
    
nums.sort()
for n in nums:
    print(n)

계수 정렬 사용 (Python3 사용해야함)

import sys
n = int(sys.stdin.readline())

nums = [0] * 10001

for _ in range(n):
    # 숫자를 입력받으면 그 값에 해당하는 리스트의 인덱스에 +1
    nums[int(sys.stdin.readline())] += 1
    
for i in range(len(nums)):
    # 입력받은 숫자만 고려하면 됨 => 0인 경우는 입력을 받지 않음
    if nums[i] != 0:
        # 해당 인덱스에 들어있는 값 => 입력받은 횟수
        # 그 값 만큼 반복해서 해당 인덱스 즉, 입력받은 값을 출력
        for j in range(nums[i]):
            print(i)

문제 해설

문제의 조건을 봤을 때, 단순하게 풀면 안 될 거 같았다. 기본적으로 구현해보니, 메모리 초과가 발생하였다. 흔히 시간 복잡도에서의 에러 발생이 많았는데 메모리 초과를 보니 좀 신선한 느낌이었다. 결국 계수 정렬을 이용해서 문제를 풀었고 정답을 맞추었다.

이 문제의 경우 2가지 배움이 있었는데

1. 단순히 list의 append를 사용할 시, 메모리의 재할당이 발생하여 공간 복잡도 면에서 불리하다.

​ - append를 사용하면 list의 크기를 하나 하나 늘려가면서 메모리르 재할당하므로 느려진다.

2. Pypy3의 경우 Python3보다 시간 복잡도면에서는 유리하나 공간 복잡도면에서는 불리하다.

​ - Stack Overflow 참고

댓글남기기

참고