10989: 수 정렬하기 3 - Python

문제

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

풀이

import sys
input = sys.stdin.readline

cnt = [0] * 10001
for _ in range(int(input())):
    cnt[int(input())] += 1

for i in range(10001):
    for _ in range(cnt[i]):
        print(i)

• .sort(), .append() 등의 함수를 사용하면 메모리 초과가 발생한다.
• 따라서 계수 정렬(Counting Sort)을 사용했다.

1. 입력의 최댓값이 10000이므로, 10001 크기의 리스트를 정의하고 0으로 초기화한다.
   -> (10001인 이유: 0부터 10000까지의 개수를 세야 하므로)
2. 정수를 N번 입력받고, 각 입력에 해당하는 인덱스에 1을 더한다.
   -> cnt의 각 인덱스에는 해당 값이 몇 번 입력되었는지 저장된다.
3. 모든 입력을 마치면, 인덱스 0부터 인덱스 10000까지 돌면서 해당 인덱스의 값(cnt[i])만큼 인덱스(i)를 출력한다.

---

오늘의 교훈

• 계수 정렬은 O(n)의 시간 복잡도를 가진다. 메모리가 부족할 때는 계수 정렬을 애용하자.
• 정렬 알고리즘에 대해 정리해서 포스팅 해야겠다.

참고 자료

• 백준 10989번 파이썬 풀이: 수 정렬하기 3
• [파이썬/Python] 백준 10989번: 수 정렬하기 3
  

더 읽어볼 것

• 알고리즘 6일차 - O(n) 정렬, 계수 정렬