[Python] 백준 #10989 수 정렬하기 3

10989번: 수 정렬하기 3 (acmicpc.net)

10989번: 수 정렬하기 3

• N개의 수 오름차순 정렬
• N의 범위 (1 ≤ N ≤ 10,000,000), 최대 10,000개 정렬

💡 알고리즘

정렬

💡 접근

퀵 정렬을 사용한 재귀함수로 풀면.. 계속 수정해봐도 메모리 초과가 뜬다.

스터디 자료를 복습하면서, 계수 정렬을 이용해보았다.

 

[계수 정렬]

• 특정 조건이 부합할 때만 사용할 수 있지만, 매우 빠른 알고리즘
• 데이터가 양의 정수, 데이터 개수가 N, 데이터의 최대값이 K일 때, 최악의 경우에도 O(N + K) 보장
• 따라서 데이터의 크기 범위가 제한된, 정수 형태일 때만 사용 가능

0으로 초기화된 리스트를 생성하고, 입력받는 수를 idx값으로 하여 +1 -> 리스트를 돌면서 0이 아닐 경우 해당 숫자만큼 idx값 출력

0 0 0 0 0 0 0 0 0 0
-> 2 2 2 1 1 2 0 1 0 0 0
-> 1 1 2 2 3 3 4 5 5 7

왜 정렬이 되는건지는 이해 안되지만 코드는 잘 돌아간다.

💡 코드

import sys

N = int(sys.stdin.readline())
nums = []
result = [0 for _ in range(10001)]

for i in range(N):
    num = int(sys.stdin.readline())
    result[num] += 1
    
for i in range(len(result)):
    for j in range(result[i]):
        print(i)

💡 정리

• 입력값을 빠르게 받기 위해 sys 모듈 사용

import sys

N = int(sys.stdin.readline())

• 0으로 초기화된 리스트를 생성할 때,

[0] * 10001 # -> 시간 초과
[0 for _ in range (10001)] # -> 정답