백준 > 10989 수 정렬하기 3

브론즈 1이라 만만하게 보고 덤볐다가 호되게 당한.. 문제였다.

 

 

이 문제의 채점 현황을 보면 메모리 초과, 시간 초과, 컴파일 에러 등등 다양한 에러를 볼 수 있다.

 

나 역시 골고루 수집한 문제..

 

우선, 파이썬으로 저 문제를 푸는 것 자체는 매우 간단하다.

a = int(input())
arr = []

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

 

하지만 이렇게 풀면 메모리 초과가 발생한다.

 

우리는 이 문제의 조건을 잘 봐야 하는데, n은 1 ~ 10,000,000개의 10,000보다 작거나 같은 자연수를 입력받게 된다.

 

입력받는 자연수의 범위가 좁기 때문에 크기가 10000인 리스트를 하나 선언하고, 입력받는 값에 따라서 해당하는 인덱스의 값을 하나씩 올려주는 방식으로 접근할 수 있다.

이를 계수정렬 이라고 한다.

 

n = int(input())
arr = [0 for i in range(10000)]

for _ in range(n):
    k = int(input())
    arr[k - 1] += 1

i = 0
test = ""
while (i < 10000):
    if arr[i] > 0:
        for _ in range(arr[i]):
            print(i + 1)
    i += 1

계수 정렬을 통해 푼 코드는 위와 같다.

 

하지만 이 코드 역시 제출하면 시간 초과가 발생하는데, print()에 시간이 오래 소요되기 때문이다.

 

때문에 최종 코드는 다음과 같다.

import sys

n = int(input())
arr = [0 for i in range(10000)]

for _ in range(n):
    k = int(sys.stdin.readline())
    arr[k - 1] += 1

i = 0
while i < 10000:
    if arr[i] > 0:
        for _ in range(arr[i]):
            sys.stdout.write(str(i + 1) + '\n')
    i += 1