[백준] 10989번_수 정렬하기 3

🔗문제 링크 바로가기

import sys
input = sys.stdin.readline

n = int(input())
 # 사용자의 입력값이 cnt의 인덱스값이 된다. 
 # 입력값의 범위가 1~ 10000이므로 cnt의 크기는 10001로 지정(배열은 인덱스 0부터 시작하기 때문에 +1)
cnt = [0] * 10001

for _ in range(n):
    # 계수 정렬의 핵심: 사용자의 입력값을 받을 리스트를 따로 지정하지 않고 바로 cnt 하나로 해결 가능
    num = int(input()) 
    cnt[num] += 1

for i in range(len(cnt)):
    if cnt[i] != 0:
        for _ in range(cnt[i]):
            print(i)

원래 아래와 같이 코드를 짰는데 메모리 부족 오류가 떠서 이를 해결하기 위해서는 sort()가 아니라 계수정렬을 써야했다.

 import sys
 input = sys.stdin.readline

 n = int(input())
 list = []
 for i in range(n):
     list.append(int(input()))

 list.sort()
 for i in range(n): 
     print(list[i])

계수정렬의 핵심

• 입력값의 크기와 개수의 범위가 정해져있을 때 사용한다
• 입력값들을 받을 배열을 따로 지정하지 않아도된다.
• 입력값은 cnt의 인덱스가 되고 cnt값은 해당 입력값이 등장한 횟수이다.
• 일반 sort()는 알고리즘 수행 도중 임의의 배열 공간을 만들기 때문에 메모리가 부족할 수 있다. 반면, 계수 정렬은 수들을 비교하지 않고 등장한 횟수로만 판단하여 정렬하기 때문에 해당 값들의 등장 횟수만 저장할 배열 cnt하나만 있으면 충분하다.