파이썬 코딩테스트 강좌, 022 수 정렬하기 3

문제 개요

이 문제는 N개의 수가 주어질 때, 이들을 오름차순으로 정렬하는 알고리즘을 작성하는 것입니다. 주어진 수의 범위는 1부터 10000까지이며, 각 수는 0보다 크고 10000 이하의 정수입니다. 이 점을 고려해 효율적인 정렬 알고리즘을 구현해야 합니다.

문제 설명

주어진 N개의 수를 정렬하여 한 줄에 하나씩 출력하는 프로그램을 작성하세요. 수의 개수는 최대 1,000,000개일 수 있습니다. 즉, 대량의 수를 정렬해야 하므로, 시간 복잡도를 고려해야 합니다.

입력

입력의 첫 줄에는 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어지고, 다음 N개의 줄에는 각 수가 주어집니다.

출력

정렬된 수를 한 줄에 하나씩 출력합니다.

예제 입력

예제 출력

문제 분석

Given the constraints, we can use a sorting algorithm that is efficient in terms of time and space. Python’s built-in sorting functionality utilizes Timsort, which has a time complexity of O(N log N) in the average and worst-case scenarios. However, considering the range of numbers is limited (from 1 to 10000), we can also explore counting sort or bucket sort for this specific task.

해법 제시

우리는 Counting Sort를 사용하여 이 문제를 해결할 것입니다. Counting Sort는 다음과 같은 방식을 사용합니다:

입력으로 받은 수의 개수를 세기 위해 카운팅 배열을 생성합니다. 배열의 크기는 10001로 설정합니다 (0~10000 포함).
각 수가 나타나는 횟수를 카운팅 배열에 저장합니다.
카운팅 배열을 반복하여 각 수를 정렬된 순서대로 출력합니다.

코드 구현

import sys

def counting_sort(n, numbers):
    count = [0] * 10001  # 0 ~ 10000 범위의 수를 위해 크기를 10001로 생성

    for num in numbers:
        count[num] += 1  # 수의 개수를 카운트

    result = []
    for i in range(10001):
        while count[i] > 0:
            result.append(i)  # count 배열의 값을 기반으로 결과 배열에 추가
            count[i] -= 1

    return result

if __name__ == "__main__":
    n = int(sys.stdin.readline())
    numbers = [int(sys.stdin.readline()) for _ in range(n)]
    
    sorted_numbers = counting_sort(n, numbers)
    print("\n".join(map(str, sorted_numbers)))

주요 포인트

Counting Sort는 안정적인 정렬 알고리즘입니다. 즉, 같은 값의 원소의 상대적인 위치가 유지됩니다.
이 알고리즘은 O(N + K)의 시간 복잡도를 가지며, 여기서 N은 입력의 크기이고 K는 수의 범위입니다.
메모리 사용량도 K가 크지 않은 한 효율적입니다.

결론

이 문제를 통해 Counting Sort 알고리즘을 실습함으로써, 정렬 성능을 극대화하는 방법을 배울 수 있었습니다. 또한, 파이썬의 기본적인 입출력 처리와 배열 사용법을 익힐 수 있었습니다. 다양한 정렬 알고리즘에 대한 이해는 프로그래밍 시험에서 중요한 요소이므로, 이러한 방식으로 문제를 접근하는 것이 많은 도움이 될 것입니다.

추가 문제: 변형 및 응용

더 나아가서, 다음과 같은 변형 문제를 시도해 볼 수 있습니다:

음수를 포함하는 수를 정렬해야 하는 경우, 입력 범위를 확장하고 카운팅 배열의 인덱스를 조정하는 방법은 무엇일까요?
다양한 정렬 알고리즘을 활용하여 같은 수를 정렬했을 때, 시간 복잡도의 차이를 분석해 보세요.
수의 범위(K)가 매우 큰 경우, Counting Sort의 대안으로 어떤 알고리즘을 사용할 수 있을까요?