백준 10989번 : 수 정렬하기3

문제.

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

10989번: 수 정렬하기 3

 

아이디어1 :

수는 10000 이하의 자연수가 입력되는데, 원소 개수는 최대 1000만개이다.

-> 원소의 종류 개수 <<< 전체 원소 개수 가 되어 같은 원소가 여러번 등장하면 계수정렬(radix sort) 사용

 

아이디어2 :

리스트는 원소 100만개를 기준으로 4MB

메모리 제한이 8MB이므로 최대 약 200만개까지 저장 가능

-> 입력받은 원소 전부(최대 1000만개)를 리스트에 저장 불가

-> 배열은 입력 받은 n의 개수를 저장하는 용도로만 사용

 

구현 :

import sys
N = int(input())
count = [0] * 10000

for i in range(N) :
  n = int(sys.stdin.readline().strip())
  count[n-1] += 1 # count[n-1]은 n의 개수이다.

for j in range(len(count)) :
  if count[j] == 0 :
    pass
  else : # 업데이트 된 원소는 출력
    for k in range(count[j]) :
      print(j+1)