[백준] 10989번 수 정렬하기 3 - Python(파이썬)

✅  문제 링크

아래 링크를 통해 문제 페이지로 이동할 수 있습니다.

📎 백준 10989번 수 정렬하기 3

 

✅  문제 설명

'수 정렬하기' 시리즈의 최종 버전입니다. 이 문제는 N개의 주어진 수를 오름차순으로 정렬하는 것으로 목표는 동일하지만, N이 최대 1,000만 개에 달하고 메모리 제한이 8MB로 매우 엄격합니다. 따라서 이전처럼 단순히 리스트에 모든 수를 저장하고 정렬하는 방식으로는 해결할 수 없습니다.

728x90

✅  문제 풀이

이 문제의 핵심은 메모리 제한을 어떻게 극복할 것인가에 있다. 천만 개의 숫자를 파이썬 리스트에 저장하려고 하면 4 bytes * 10,000,000 = 40MB로, 주어진 8MB 메모리를 훌쩍 넘겨버린다. 여기서 우리는 문제의 또 다른 조건을 활용해야 한다: 입력되는 수는 10,000보다 작거나 같은 자연수라는 점이다.

이처럼 수의 범위가 제한적일 때 아주 효과적인 카운팅 정렬(Counting Sort) 알고리즘을 사용하면 된다.

• 카운팅 배열 만들기: 먼저, 1부터 10,000까지의 숫자가 각각 몇 번 등장했는지 기록할 수 있는 배열(리스트)을 만든다. 크기가 10,001인 리스트를 만들고 모든 값을 0으로 초기화해두면 된다.
• 숫자 개수 세기: 이제 N개의 숫자들을 입력받으면서, 해당하는 숫자의 인덱스에 카운트를 1씩 증가시킨다. 예를 들어, 숫자 5가 입력되면 5번 인덱스의 값을 1 늘려주는 식이다. 이 과정에서는 천만 개의 숫자를 저장할 필요 없이, 카운팅 배열 하나만 유지하면 되므로 메모리 문제가 해결된다.
• 결과 출력하기: 모든 입력이 끝나면, 카운팅 배열의 1번 인덱스부터 10,000번 인덱스까지 순회한다. 각 인덱스에 기록된 숫자(카운트)만큼 해당 인덱스 번호(실제 숫자)를 반복해서 출력해주면, 자연스럽게 오름차순으로 정렬된 결과가 나온다.

이 문제 역시 입력이 매우 많으므로, 시간 초과를 피하기 위해 sys.stdin.readline()을 사용하는 것이 필수적이다.

✅  정답 코드

import sys

# 수의 개수 N을 빠르게 입력받는다.
n = int(sys.stdin.readline())

# 1부터 10,000까지의 수 등장을 카운트할 리스트를 생성한다.
# 인덱스와 숫자를 일치시키기 위해 크기는 10001로 설정한다.
count_list = [0] * 10001

# N개의 줄에 걸쳐 숫자를 입력받으면서 카운팅한다.
for _ in range(n):
    num = int(sys.stdin.readline())
    count_list[num] += 1

# 카운팅 리스트를 순회하며 결과를 출력한다.
for i in range(1, 10001):
    # 만약 해당 숫자가 한 번이라도 등장했다면
    if count_list[i] != 0:
        # 등장한 횟수만큼 해당 숫자를 출력한다.
        for _ in range(count_list[i]):
            print(i)