Python) 10989 수 정렬하기 Counting Sort (계수 정렬)

이번 문제는 수를 정렬하는 문제입니다.

계수 정렬도 풀어야지 해결할 수 있습니다! (몰랐어요..ㅠㅠ)

 

계수 정렬이란?

데이터의 범위가 작고 정수일 경우 효율적인 정렬 알고리즘이며, 시간 복잡도는 O(n+k)입니다. (n은 입력 데이터의 수, k는 입력 데이터의 범위)

계수 정렬의 기본 원리는 입력 데이터의 각 정수 값을 계수하기 위해 배열을 사용하는 것입니다.

배열의 각 인덱스는 입력 정수 값에 대응하며, 배열의 값은 해당 정수가 데이터에 나타나는 회수를 나타냅니다.

제가 해결한 방법은

1.  숫자 목록(N개의 정수 값)을 입력 받습니다.
2.  크기가 100인 배열(arr)을 생성합니다. 배열의 크기는 입력 데이터의 최대 범위에 따라 조정될 수 있습니다.
3. 입력 받은 숫자 목록에서 각 숫자를 읽고, 해당 숫자와 같은 위치의 인덱스에 있는 배열의 값을 증가시킵니다. 이 과정을 통해 각 숫자의 등장 횟수를 기록합니다.
4. 배열을 처음부터 끝까지 순회하며 각 인덱스에 해당하는 횟수만큼 숫자를 출력하는 방식으로 정렬된 리스트를 생성합니다.

import sys

# 표준 입력에서 첫 번째 줄을 읽어 숫자 개수 N에 대한 정수 값을 얻습니다.
N = int(sys.stdin.readline().strip())

# 크기가 100,000인 계수 배열 선언 (입력 데이터의 범위가 큰 경우 사용)
arr = [0] * 100000

for i in range(N):
    # 표준 입력에서 각 숫자를 한 줄씩 읽어와 정수 값을 얻습니다.
    value = int(sys.stdin.readline().strip())
    # 입력한 값(value-1)에 해당하는 인덱스의 배열 값을 증가시킵니다.
    arr[value - 1] += 1

# 계수 배열을 순회하며 정렬된 결과를 출력합니다.
for index in range(len(arr)):
    # 배열의 값이 0이면 해당 인덱스(index+1)의 값은 없는 것으로 판단하고 건너뜁니다.
    if arr[index] == 0:
        continue
    else:
        # 해당 인덱스(index+1)에 저장된 값(회수)만큼 반복하여 값을 출력합니다.
        for j in range(arr[index]):
            print(index + 1)