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

백준 10989번 문제입니다. (solved.ac)기준 실버 5 문제입니다.

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

문제 접근

 처음에는 단순히 정렬을 직접 구현해서 제출도 해보고 파이썬의 sort함수를 사용하여 제출도 해보았는데 시간 초과 오류와 메모리 초과 오류가 발생하였습니다. 찾아보니 계수 정렬(Count Sort)로 문제를 해결해야 한다고 합니다.

 계수 정렬(Count Sort)은 이 링크 에서 자세히 확인해 볼 수 있습니다. 계수 정렬은 비교 기반의 정렬 알고리즘이 아니고 간단한 원리로 매우 빠르게 동작합니다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용이 가능합니다.

 첫째 줄에 수의 개수 N이 주어지고 둘째 줄 부터 N 개의 줄에는 정렬해야 할 수가 주어집니다. 이 수는 10,000보다 작거나 같은 자연수입니다. 주어지는 N개의 수들은 10,000보다 작거나 같은 자연수이기 때문에 효과적으로 계수 정렬을 사용할 수 있습니다.

 수를 입력 받은 후 리스트를 비교하며 정렬하는 형태가 아니라 단순하게 수의 최대 범위(10,000)만큼 리스트를 만들고 각 인덱스에 인덱스 숫자가 입력받은 횟수를 적어 순차적으로 출력해주면 됩니다.( cnt[4]에는 4가 입력 받은 횟수가 기록 됨)

 cnt리스트를 10001개만큼 생성했다고 가정한 후 2를 입력 받았다면 cnt[2] += 1이 된다는 소리입니다. 수를 다 입력 받은 후 cnt의 1부터 10,000까지의 모든 인덱스에 접근하여 각 인덱스의 담긴 숫자만큼 반복하여 출력해주면 됩니다. ex) cnt[3] = 5 라면 3을 5번 출력(5줄)

 

정답 코드(Python)

import sys
# 명령의 수(n)
n = int(sys.stdin.readline().rstrip())

# 계수정렬을 하기위하여 리스트 생성
# ex) cnt[4]는 4가 주어진 횟수가 담겨짐
cnt = [0] * 10001

# n번만큼 수를 입력 받음(10,000이하의 자연수)
for _ in range(n) :

    input_data = int(sys.stdin.readline().rstrip())
    # cnt리스트의 입력된 수 인덱스에 접근하여 +1을 해줌. 한 번 입력되었다는 듯
    cnt[input_data] += 1

# 1부터 10,000까지 cnt의 모든 인덱스에 접근하여
# 인덱스 숫자(i)를 cnt[i] 번 반복 해줍니다(0이 아니라면).
# 0이라면 입력 받은 적이 없다는 소리
for i in range(1, 10001) :
    if cnt[i] != 0:
        for _ in range (cnt[i]):
            print(i)