[단계별로 풀어보기][python 3] 정렬 - 수 정렬하기 3 (10989)

 

10989번: 수 정렬하기 3 (acmicpc.net)

10989번: 수 정렬하기 3

정렬 문제들에서 주의할 점은 시간과 메모리다.

이 문제에서는 메모리가 단 8MB에 시간제한이 5초인 점에 주의해야 한다.

도전 1

def quickSort(li):
    if len(li) <= 1: return li
    
    pivot, tail = li[0], li[1:]
    left = [i for i in tail if i <= pivot]
    right = [i for i in tail if i > pivot]
    
    return quickSort(left) + [pivot] + quickSort(right)

n = int(input())

first = [0]*n
for i in range(n):
    first[i] = int(input())

first = quickSort(first)

for i in first:
    print(i)

퀵 정렬을 사용해 정렬을 시도했다.

메모리 초과로 실패했다.

 

도전 2

카운트 정렬을 사용해 메모리를 절약해보려고 시도했다.

n = int(input())

first = [0]*10001

for i in range(n):
    first[int(input())] += 1

for i in range(10001):
    if first[i] != 0:
        for j in range(first[i]):
            print(i)

시간 초과로 실패

 

최종

input() 함수가 조금 느리다는 정보를 접수해서 input() 대신 sys.stdin.readline() 함수를 이용했다.

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

first = [0]*10001

for i in range(n):
    first[int(sys.stdin.readline())] += 1

for i in range(10001):
    if first[i] != 0:
        for j in range(first[i]):
            print(i)