백준 10989: 수 정렬하기 3 Python (메모리 초과)

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

10989번: 수 정렬하기 3

 

 

처음에는 직관적으로 sort() 함수를 사용했다.

하지만 이렇게 하니까 계속 메모리 초과가 났다.

N을 제외한 input의 개수가 1~10,000,000이기 때문인 것 같다.

# 오류난 코드(메모리 초과)
import sys
input = sys.stdin.readline


N = int(input())
arr = list(int(input()) for _ in range(N))
arr.sort()
for i in range(N):
    print(arr[i])

 

일반적으로 정렬 문제의 경우 counting 정렬을 활용하면 풀리기 때문에 이번에도 counting sort를 사용하고자 했다.

N을 제외한 input 수는 최대가 10,000이기 때문에 counting 배열을 [0] * 10,001로 만들어준다.

# 통과 코드
import sys
input = sys.stdin.readline


N = int(input())
counts = [0] * 10001

for i in range(N):
    counts[int(input())] += 1

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