Python 공간 복잡도 개선

10989번: 수 정렬하기 3

이전부터 시간, 공간 복잡도 계산을 미루어왔기에, 간단한 문제임에도 제한적인 공간 복잡도를 해결하지 못하는 상태이다.

문제 분석

문제 |
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력 |
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다.
둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력 |
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

첫 시도

import sys

input = sys.stdin.readline

N = int(input())
data = [int(input().strip()) for _ in range(N)]
data.sort()

for d in data :
    print(d)

가장 기본적인 코드이다. 입력 받은 후 sort()를 통해 정렬, 이후 반복문 돌며 하나씩 출력하는 로직이다.

하지만 메모리 초과로 실패.

문제 분석

(1) 시간 복잡도 분석
sorted 내장 함수의 시간 복잡도를 따라, O(NlogN)
즉, 최대 70,000,000 이므로 4초 이내에 계산 가능

(2) 공간 복잡도 분석
data list의 경우, N 만큼의 공간이 필요.
sort() 함수 사용 시, N 만큼의 추가 공간 필요.
즉, O(N)이므로 길이가 10,000,000개인 리스트는 메모리 40MB 정도를 필요로 한다.

때문에 8MB의 메모리 제한을 초과할 수 밖에 없는 것이다.

두 번째 시도

import sys

input = sys.stdin.readline
N = int(input())
data = [-1] * 10000000
for i in range(N) :
    data[i] = int(input().strip())

data.sort()

for d in data :
    if d > -1 :
        print(d)

사전에 data를 할당하였기에 메모리 사용량이 증가하지 않았기에, 빅오 표기법 상으로는 O(1)이다. 하지만, 길이가 10000000인 리스트를 저장해야 하는 것은 동일하므로 여전히 메모리 초과가 발생하였다.

세 번째 시도

import sys

input = sys.stdin.readline
N = int(input())
data = [0] * 10001
l = list(int(input().strip()) for _ in range(N))
for n in l :
    data[n] += 1

for i in range(1, 10001) :
    for _ in range(data[i]) :
        print(i)
       

네 번째 시도

import sys

input = sys.stdin.readline
N = int(input())
data = [0] * 10001
for _ in range(N) :
    data[int(input().strip())] += 1

for i in range(1, 10001) :
    for _ in range(data[i]) :
        print(i)