[알고리즘] 계수정렬으로 메모리 초과 해결하기 (백준 10989 Python)

안녕하세요 블하블하~.

오늘은 계수 정렬에 대해 알아봅시다.

 

---

 

 

1. 계수정렬이란?

미리 큰 배열을 만들어 놓고, 입력받은 수를 바로 그 인덱스 값에 1로 저장을 하는 방법이다. 이 방법을 사용하면 최빈값을 구하거나, 값을 정렬할 때 입력으로 큰 수가 들어와도 메모리 초과 없이 값을 구할 수가 있다. 

 

관련 글로는 이 계수정렬을 이용해서 최빈값을 구하는 방법도 있다.

https://perconsi.tistory.com/114

[알고리즘] 최빈값 구하는 알고리즘 (직접 구현/Counter 클래스로 구하는 법) - Python

 

 

2. 계수정렬을 이용해서 입력 받은 수 오름차순으로 정렬

그래서 오늘은 백준의 10989번을 이용해서 Python의 계수 정렬을 풀어 보았다.

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

10989번: 수 정렬하기 3

 

이것도 그냥 반복문으로 입력 받아서 sort를 쓰면 바로 메모리 초과가 난다 ㅎㅎ,,,,

그래서 이 문제는 계수 정렬을 사용하여 가장 큰 입력 값인 10,000 크기만큼의 배열을 미리 만들어 두고, 각 요소마다 0을 할당해놓고 입력값을 받을 때마다 그 입력값과 같은 인덱스에 +1씩 해준다. 그리고 마지막에 배열을 모두 반복문을 돌면서 값이 있을 때 그 값을 정렬하면 메모리 초과 없이 빠르게 값을 정렬할 수 있다.

그래서 핵심은 입력 받은 수를 그 수에 해당하는 인덱스에 저장해 두고, 전체 배열에서 인덱스가 있는 값만 순차적으로 출력하면 빠르게 값을 정렬할 수 있고, 이 방법을 계수 정렬이라고 한다.

 

구현 코드는 아래와 같다!

import sys
T=int(input())
arr=[0]*10001

for _ in range(T):
    arr[int(sys.stdin.readline())]+=1

for i in range(10001):
    if arr[i]:
        for j in range(arr[i]):
            print(i)