개발 지식/알고리즘

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

Prcnsi 2023. 2. 10. 22:11
728x90

안녕하세요 블하블하~.

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

 


 

 

1. 계수정렬이란?

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

 

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

https://perconsi.tistory.com/114

 

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

오늘은 Python의 인덱스를 이용하여 최빈값을 구하는 법을 알아 보겠습니다. numpy의 최빈값을 구해주는 함수 mode를 사용하면 편리하지만, 직접 구할 때는 어떤 로직을 사용해야 하는지 정리해봤고

perconsi.tistory.com

 

 

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

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

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

 

10989번: 수 정렬하기 3

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

www.acmicpc.net

 

이것도 그냥 반복문으로 입력 받아서 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)
728x90