소스코드
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')
Python
복사
풀이
•
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')
Python
복사
그러나 이렇게 풀면 메모리 초과가 나옵니다. 정확히는 설명하지 못 하지만 어쨌든 메모리 초과가 발생했다는건 각 정수들을 천만개로 한 번에 관리하기 때문일 것입니다. 이럴 경우에 사용해볼만한 정렬 알고리즘은 계수 정렬이 있습니다. 계수 정렬은 다음과 같은 장단점이 있습니다 :
▪
장점
•
시간복잡도 O(N + K) : N(데이터 개수), K(데이터 중 최대값)
•
안정 정렬 : 값이 같은 요소들의 순서를 보장
•
메모리를 효율적으로 사용 : 리스트 하나로 카운트 가능
▪
단점
•
정수 범위가 제한적 : 너무 큰 경우, 카운트하기 위한 리스트 사이즈도 매우 커짐
•
음수 정렬 불가능 : 음수를 인덱스로 사용 불가능하므로
•
메모리 낭비 가능 : 데이터 개수 N이 작더라도, 한 인덱스의 데이터 최대 개수 K가 너무 크면 메모리를 낭비하게 됨
•
정수 이외 데이터 사용 불가
•
계수 정렬은 원소의 값에 해당하는 인덱스의 카운트를 1 증가하면 됩니다. 출력할 때는 각 인덱스의 카운트 값만큼 반복해서 출력하면 됩니다.