백준 알고리즘 - 10989 - 수 정렬하기 3

문제풀이 횟수 : 

 

---

문제 풀이 핵심 아이디어

파이썬은 대략 1초에 약 2천만개까지 연산을 수행할 수 있다.

따라서 파이썬의 기본 정렬 라이브러리를 사용하면 이 문제를 풀 수 없다.

 

시간 복잡도가 O(N)의 정렬 알고리즘을 이용해야 하고,

데이터의 개수가 최대 1천만개 이므로 기본 정렬 라이브러리를 사용하면 안된다.

또한 수의 범위가 1~10000 이고, 범위가 작으므로 계수정렬(Counting sort)을 이용할 수 있다.

 

 

 

유의사항

데이터의 개수가 많을 때 파이썬에서는 sys.stdin.readline() 으로 읽어야 한다.

input()함수에 비해서 빠르기 때문이다.

 

---

코드

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

for i in range(n):
    data = int(sys.stdin.readline())
    arr[data] += 1 # 인덱스에 해당하는 배열의 값을 증가 = 갯수 증가

for i in range(10001): 
    if arr[i]!=0: 
        for j in range(arr[i]): # 등장 횟수 만큼 인덱스 값 출력
            print(i)