11989- 수 정렬하기

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

브론즈 문제지만 counting sort에 대해 알고있지 않다면 풀 수 없는 문제이다. 리스트의 정렬을 생각하면 우선 그 리스트를 온전히 다 입력받은 상태에서 어떤 정렬 방식을 쓰는 것이 가장 효율적일까를 생각하겠지만 이 문제의 경우 입력값의 개수 N 이 최대 10,000,000이기 때문에 이를 다 입력받으면 메모리 초과가 발생한다. 

 

그렇다면 모든 원소들을 입력받지 않고 정렬을 진행해야 한다는 것인데.. 힌트는 입력받는 수의 범위에 있다. 각각의 수는 10,000보다 작거나 같은 자연수이다. 따라서 길이가 10001인 배열을 하나 만들어 놓고 계수정렬을 진행하면 메모리 초과 없이 문제를 해결할 수 있다. 

 

import sys
# 입출력 값이 많기 때문에 시간초과를 방지하기 위해 설정
input = sys.stdin.readline
print = sys.stdout.write

N = int(input())
count = [0 for _ in range(10001)]

for _ in range(N):
    n = int(input())
    count[n] += 1	# 입력받은 자연수에 해당하는 배열값을 +1 해준다

for i in range(1, 10001):
    for j in range(count[i]):	# count[i]의 값만큼 출력 반복
        print(str(i))
        print("\n")