백준 10989 : 수 정렬하기3(카운팅정렬)

수 정렬하기 3

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

 

---

코드

# https://teching.tistory.com/
import sys
# 계수정렬
countingNum = [0] * 10001
for _ in range(int(sys.stdin.readline().rstrip())):
    countingNum[int(sys.stdin.readline().rstrip())] += 1
for i in range(10001):
    for _ in range(countingNum[i]):
        print(i)

해설

메모리 제한이 8MB로 빡빡한 문제이다. 

계수 정렬을 구현해서 풀었다. 계수 정렬에 관한 내용은 https://teching.tistory.com/80에서 정리를 해두었다!

정렬 알고리즘 3 : 계수 정렬(Counting sort)

처음에는 입력값들을 리스트에 저장해서 세는 방법을 사용했는데 입력을 리스트에 저장하면 그 자체만으로 메모리 허용량을 초과해버린다. (최대 천만 개가 들어오기 때문에)

그래서 입력은 저장하지 않고 각 숫자가 몇 번 들어왔는지 세는 countingNum리스트만 저장을 했다.