정렬

약수, 배수와 소수2

10989: 수 정렬하기3

문제

예제

풀이

메모리초과가 나와서 풀이를 찾아보니 범위가 적다면 카운팅 정렬을 사용하여 풀 수 있다고 한다.

import sys
input = sys.stdin.readline
n = int(input())
count = [0] * 10001

for _ in range(n):
    num = int(input())
    count[num] += 1
    
for i in range(1, 10001):
    if count[i] != 0:
        for _ in range(count[i]):
            print(i)

끄적끄적

카운팅 정렬

카운팅 정렬은 숫자의 등장 횟수를 저장한 후, 누적하여 정렬하는 방식이다. 데이터의 최댓값(K)이 크지 않은 경우 O(N+K)의 시간 복잡도로 빠르게 정렬할 수 있다.
하지만 데이터 범위가 클 경우 메모리 사용량이 많고 음수 데이터 정렬이 어렵다.
자세한 설명은 여기로 ➡️ 카운팅 정렬