[알고리즘] 계수정렬(Counting Sort) .feat 백준 10989번(파이썬)

계수 정렬이란?

- 원소들간의 비교를 하지 않고, 숫자의 개수를 파악하여 정렬을 수행하는 알고리즘이다. 

- 타 정렬들과 다르게 비교하지않아서 시간복잡도는 O(N)이다. 

- 10989번의 문제는 시간제한이 있어 계수정렬을 이용하여 풀기로 생각하였다!

 

계수 정렬 수행과정

1. 입력받은 혹은 정렬을 하고 싶은 데이터 리스트에서 최대값 + 1 하여 리스트를 만든다.

2. 최대값 + 1 리스트에 데이터가 몇개가 겹치는지 횟수를 기록한다.

3. 그 횟수를 토대로 인덱스를 출력한다. 

 

아래는 위의 계수 정렬을 파이썬코드로 구현한겁니다.

import sys
input = sys.stdin.readline
N = int(input())
Nlist = []
 
if 1<=N and N<=10000000:
    for i in range(N):
     Nlist.append(int(input()))
     if Nlist[i] > N:
        print("error")
        continue
 
    Countlist = [0] * (len(Nlist) + 1)
    for i in range(N):
       Countlist[Nlist[i]] += 1 ##횟수 체크
    for i in range(len(Countlist)):
       for j in range(Countlist[i]):
          print(i) ##횟수를 토대로 출력
else:
    print("Error")
 
 

메모리 초과 오류가 떴군요... 흠냐흠냐 :(

append가 메모리를 많이 먹는다는군요. 이제부터append는 지양해야겠습니다.

 

import sys
 
N  = int(sys.stdin.readline())
arr = [0]*10001
 
for _ in range(N):
    num = int(sys.stdin.readline())
    arr[num] += 1 # arr[num]에 num이 들어온 개수 count 
 
for i in range(10001): 
    # arr[i]에 숫자가 들어왔다면 
    if arr[i] != 0:
        # arr[num]에 num이 들어온 개수 만큼 출력 
        for j in range(arr[i]): 
            print(i)

아래와 같이 바꾸어주었습니다. 흑흑 길이때문에 조금 줄였어용