소스코드

import sys
input = sys.stdin.readline

N = int(input().strip())
arr = [0 for _ in range(10000)]
for _ in range(N):
    num = int(input().strip())
    arr[num-1] += 1

for i in range(10000):
    if arr[i] > 0:
        for _ in range(arr[i]):
            sys.stdout.write(str(i+1) + '\\n')

풀이

• N의 개수가 10^7(천만)이고 각 숫자는 10000보다 작거나 같은 자연수입니다. 물론 기본 정렬 메서드(sort 또는 sorted)를 사용하면 충분히 시간 제한을 통과할 수 있습니다.

  • 기본 정렬 메서드를 사용한 풀이는 다음과 같습니다 :

    import sys
    input = sys.stdin.readline
    
    N = int(input())
    arr = [int(input()) for _ in range(N)]
    
    arr.sort()
    
    sys.stdout.write('\\n'.join(map(str, arr)) + '\\n')
    

    그러나 이렇게 풀면 메모리 초과가 나옵니다. 정확히는 설명하지 못 하지만 어쨌든 메모리 초과가 발생했다는건 각 정수들을 천만개로 한 번에 관리하기 때문일 것입니다. 이럴 경우에 사용해볼만한 정렬 알고리즘은 계수 정렬이 있습니다. 계수 정렬은 다음과 같은 장단점이 있습니다 :

    • 장점
      • 시간복잡도 O(N + K) : N(데이터 개수), K(데이터 중 최대값)
      • 안정 정렬 : 값이 같은 요소들의 순서를 보장
      • 메모리를 효율적으로 사용 : 리스트 하나로 카운트 가능
    • 단점
      • 정수 범위가 제한적 : 너무 큰 경우, 카운트하기 위한 리스트 사이즈도 매우 커짐
      • 음수 정렬 불가능 : 음수를 인덱스로 사용 불가능하므로
      • 메모리 낭비 가능 : 데이터 개수 N이 작더라도, 한 인덱스의 데이터 최대 개수 K가 너무 크면 메모리를 낭비하게 됨
      • 정수 이외 데이터 사용 불가
• 계수 정렬은 원소의 값에 해당하는 인덱스의 카운트를 1 증가하면 됩니다. 출력할 때는 각 인덱스의 카운트 값만큼 반복해서 출력하면 됩니다.