[백준][Python] 10989

PS를 준비를 위해 백준에서 문제를 풀던 중 쉬운 문제에서 난관에 봉착하게 되었다. 겉보기에는 쉬운 정렬 문제로 여겨졌는데 메모리 초과와 시간 초과에 걸린 상황이다. 문제는 아래와 같다.

처음에는 메모리를 신경쓰지 않고 그냥 단순한 정렬이라고 생각해 sort()를 이용할 생각을 했다. 코드는

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

결과는 메모리 초과였다. sort()에서의 반복을 줄이고자 입력으로 받는 수의 인덱스에 +1을 해주는 식의 풀이 방법을 생각해냈으나, 이는 시간초과에 걸리게 되었다. 아래는 그 코드다.

N = int(input())
arr = [0] * 10001
for i in range(N):
    arr[int(input())] += 1

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

이에 for문을 통해 받는 int(input())을 sys 라이브러리의 int(sys.stdin.readline())를 통해 속도를 해결, 문제를 해결할 수 있게 되었다.

import sys

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

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

메모리가 부족할 경우에 해당 풀이법을 떠올릴 수 있는 좋은 경험을 하게 된 것 같다.