백준 10989번: 수 정렬하기 3

📚 백준 10989번: 수 정렬하기 3

📖 문제 개요

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 문제입니다. 단, 주어지는 숫자는 10,000 이하의 자연수입니다. 문제의 자세한 내용은 여기에서 확인하세요.

🎯 문제 핵심

이 문제의 핵심은 주어진 숫자들을 메모리 제한 내에서 효율적으로 오름차순으로 정렬하는 것입니다.

✏️ 해결 방법

계수 정렬(counting sort)을 사용하여 효율적인 정렬을 수행합니다. 주어진 숫자의 범위가 제한적이므로, 각 숫자가 몇 번 등장하는지 카운트하여 출력하는 방식을 사용합니다.

import sys
input = sys.stdin.readline

n = int(input())
count = [0] * 10001

for _ in range(n):
    num = int(input())
    count[num] += 1

for i in range(10001):
    if count[i] > 0:
        for _ in range(count[i]):
            sys.stdout.write(str(i) + '\n')

📝 코드 설명

1. 숫자의 개수 $n$을 입력받습니다.
2. 숫자의 최댓값 10,000을 고려하여 크기가 10,001인 count 리스트를 0으로 초기화합니다.
3. 주어진 $n$개의 숫자를 입력받아 해당 숫자의 인덱스 위치의 count 값을 1씩 증가시킵니다.
4. count 리스트를 순회하면서 각 숫자가 몇 번 등장하는지 확인하고 그만큼 숫자를 출력합니다.

🚀 실행 방법

위의 코드를 복사하고 Python 환경에서 실행하세요. sys.stdin.readline()은 입력을 빠르게 받기 위한 함수입니다.