[Python]10989번, 카운팅 정렬 응용

문제

 

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 

둘째 줄부터 N개의 줄에는 수가 주어진다. 

이 수는 10,000보다 작거나 같은 자연수이다.

 

출력

 

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

풀이

 

문제 소개에 카운팅 정렬을 사용하면 된다고 해서 순수하게 구현해놓은 카운팅 정렬을 써보았다.

 

단 한 문제도 통과하지 못하고 메모리 초과.

 

어떻게든 스텝을 줄여보려고 for문을 합쳐보기도 하고 리스트의 요소 개수를 조절해봐도

 

여전히 메모리 초과와 시간 초과.

 

그래도 도전해보겠다고 한시간 내내 매달리다가 포기하고 그냥 카운팅 정렬의 아이디어만 응용하기로 했다.

 

풀이 단계는 아래와 같다.

 

• 문제에서 주어질 수의 최댓값(10000)에 해당하는 Counting 리스트를 미리 생성한다.
• 입력으로 주어지는 수를 별개의 리스트로 생성하지 않고 바로 Counting 리스트로 개수를 세어준다.
• 0번 인덱스부터 순회하며 0이 아닌 Counting 리스트의 인덱스 값을 요소 값 만큼 바로 출력한다.

이런 식으로 했더니 겨우 통과가 되었다.

 

하지만 이렇게 하면 안정정렬을 보장하지 못하기 때문에 카운팅 정렬 그 자체라기 보다는

 

거기서 아이디어를 차용한 별개의 정렬이라고 보는 것이 맞을 수도 있겠다.

 

내 한시간..

 

허무하지만 코드는 굉장히 짧다.

import sys

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

for _ in range(n):
    counting[int(sys.stdin.readline())] += 1

for i in range(10001):
    if counting[i] != 0:
        for j in range(counting[i]):
            print(i)