[백준10989_파이썬(python)] - 수 정렬하기 3

🔴 문제

수 정렬하기 3

🟡 Sol

import sys

N = int(input())
N_list = [0] * 10000

for i in range(N):
  n = int(sys.stdin.readline())
  N_list[n-1] += 1

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

🟢 풀이

처음에 sort() 함수를 풀었더니 "메모리 초과" 로 틀렸다. 수 정렬하기 2는 메모리 제한이 256MB였지만 이 문제는 메모리 제한이 8MB이기 때문에 sort()를 사용하면 메모리 초과가 난다고 한다.

그래서 검색해본 결과 "계수정렬" 이라는 것을 사용하면 된다고 하더라
사실 풀이는 보지 않았는데 계수정렬이라는 단어를 보자마자 어떻게 풀어야할지 생각났다.

생각한대로 푸니 정답이었고 다른분들 코드랑 비교하니 정말 똑같았음
신기하당

암튼 계수정렬은 그 숫자의 인덱스 위치의 값을 증가시키고, 마지막에 리스트를 순회 하면서 0이 아닌 값만 개수대로 출력하면 된다.

🔵 Ref

https://blockdmask.tistory.com/424
https://coarmok.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%ACpython-%EB%B0%B1%EC%A4%80-10989%EB%B2%88-%EB%A9%94%EB%AA%A8%EB%A6%AC-%EC%B4%88%EA%B3%BC