백준 | 수 정렬하기 3

백준 수 정렬하기 3

이 문제는 N개의 정수를 오름차순으로 정렬해야 하는 문제이다.

많은 알고리즘 문제에서 시간 복잡도를 우선 고려하고, 파이썬의 sort()는 O(N log N)의 시간 복잡도를 가지므로, 다음과 같은 코드를 떠올릴 수 있다.

# 오답(메모리 초과)


import sys

# 입력
n = int(sys.stdin.readline().strip())
nums = [int(sys.stdin.readline().strip()) for _ in range(n)]

# 정렬
nums.sort()

# 출력
for num in nums:
    print(num)

이 코드는 시간 초과가 아닌 메모리 초과가 발생한다.
리스트에 N개의 정수를 저장하는 것만으로 8MB(메모리 제한)를 초과하기 때문이다.

파이썬에서 정수(int)가 4바이트(4B)를 차지한다고 가정하자.
최악의 경우 4B * 10,000,000 = 40,000,000B만큼의 메모리를 필요로 하며, 1MB = 1,000,000B라 잡아도 약 40MB가 필요하다.

이러한 문제를 어떻게 해결할 수 있을까?

문제의 조건을 다시 보면, 입력값의 범위(1 이상 10,000 이하)가 작고, 중복된 숫자가 나올 가능성이 크다.
따라서 정렬 없이 숫자의 개수만 세서 출력하는 계수 정렬(Counting Sort)을 떠올릴 수 있다.

계수 정렬은 입력값의 개수 N, 입력값의 범위 K에 대해 O(N + K)의 시간 복잡도를 가질 뿐만 아니라, O(K)의 공간 복잡도를 가지므로, 8MB도 초과하지 않는다!

# 정답


import sys

# MAX_NUM: 입력의 최댓값
MAX_NUM = 10000

# counting: 계수 정렬을 위한 리스트
counting = [0] * (MAX_NUM + 1)

# 입력
n = int(sys.stdin.readline().strip())

# 입력받은 숫자 개수
for _ in range(n):
    num = int(sys.stdin.readline().strip())
    counting[num] += 1

# 출력
for num in range(1, MAX_NUM + 1):
    if counting[num] > 0:
        for _ in range(counting[num]):
            print(num)