[백준] 10989번 - 수 정렬하기 3

📩 출처

문제

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

입력

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

출력

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

👉 생각

• 단순히 오름차순 문제는 아닐꺼라 생각해서 카운트 정렬 방법을 사용했는데, 오히려 이문제는 메모리 초과를 신경써야 하는 문제였다.

# 카운팅 정렬, but 메모리 초과
count = [0] * (max(numbers.values)+1)
tmp = [0] * len(numbers.values)
for i in numbers.values:
    count[i] += 1
for i in range(1,len(count)):
    count[i] += count[i-1]

for number in range(len(numbers)-1, -1, -1):
    tmp[count[numbers[number]]-1] = numbers[number]
    count[numbers[number]] -= 1
for i in tmp:
    print(i)

• 따라서 입력받는 정수를 리스트에 추가하여 메모리를 늘려가는 것이 아닌 딕셔너리의 값으로 카운트 해주었다. 정렬시켜야할 수의 누적 값을 알고 있기 때문에 카운팅 정렬 할 수 있었지만 시간 초과를 신경 써야할 문제는 아니여서 내장함수를 사용했다.

import sys
n = int(input())
numbers = {}
for _ in range(n):
    number = int(sys.stdin.readline())
    numbers[number] = numbers.get(number, 0) + 1
for i in sorted(numbers.keys()):
    for _ in range(numbers[i]):
        print(i)