[백준]10989번 수 정렬하기 3 - 정렬

문제 설명

 

import sys

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

for i in range(n):
    index = int(sys.stdin.readline())
    a[index] += 1
    
for j in range(10001):
    if a[j] != 0:
        for x in range(a[j]):
            print(j)
    

 

코드 설명 

input() 함수 대신 sys.stdin.readline() 함수를 이용함으로써 입력 받는 속도를 빠르게 처리할 수 있다. 먼저 수의 한계가 10000이므로 10001 크기의 리스트를 0으로 초기화 하여 준다. 반복문을 돌면서 입력받는 수를 인덱스로 하여 1씩 증가시켜 해당 수가 몇번 등장했는지 세준다. 그 후 배열을 돌면서 0번 등장한 수는 제외하고 나머지 수를 인덱스 순서대로 출력해주면 정렬된 결과를 얻을 수 있다.

 

Point : 이 문제는 카운팅 정렬을 이용하여 제한된 메모리와 시간안에 해결하여야 한다. 그렇기 때문에 O(n)의 시간 복잡도를 갖는 카운팅 정렬을 사용하여야 한다. 수의 크기가 10000까지 이므로 해당 크기만큼 리스트를 초기화 하고 등장한 수 만큼 카운트를 해주고, 인덱스 순서대로 리스트를 출력하면 문제를 해결할 수 있다.