백준 10989번 수 정렬하기 3(python)

1. 문제

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

2. 풀이

처음에 단순한 정렬문제라 생각했고 메모리 초과가 나왔다.

import sys

n = int(sys.stdin.readline())
arr = []
for i in range(n):
    arr.append(int(sys.stdin.readline()))

arr.sort()
for i in arr:
    print(i)

그래서 다른 정렬방법을 찾아보던 중 카운팅 정렬이란 것에 대해 알게 되었다.

3. 코드

import sys

n = int(sys.stdin.readline())
cnt = [0] * 10001

for i in range(n):
    num = int(sys.stdin.readline())
    cnt[num] += 1

for i in range(10001):
    if cnt[i] != 0:
        for j in range(cnt[i]):
            print(i)

4. 알게된 점

📚 카운팅 정렬이란? 요소의 갯수를 세어 선형 시간에 정렬하는 효율적인 알고리즘으로 시간 복잡도가 o(n + k)이다.

https://seongonion.tistory.com/130