첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
예제
input
output
10 5 2 3 1 4 2 3 6 1 7
1 1 2 2 3 3 4 5 5 7
나의 코드
간단하게 sorted와 lamda식을 써서 한 번 돌려보았다.
import sys
n = int(sys.stdin.readline())
numbers = [_ for _ in range(n)]
for i in range(n):
numbers[i] = int(sys.stdin.readline())
numbers = sorted(numbers, key=lambda numbers: numbers)
for i in range(n):
print(numbers[i])
첫 시도에서 메모리 초과가 발생했다. 메모리 제한이 8MB라서 여태 사용해온 정렬로는 통과할 수 없는 것 같다.
import sys
n = int(sys.stdin.readline())
a = [0]*n
b = [0]*(n+1)
counting = [0]*10001
for i in range(n):
a[i] = int(sys.stdin.readline())
counting[a[i]] += 1 # count
for i in range(1, 10001): # 누적 합
counting[i] += counting[i - 1]
for i in range(n - 1, -1, -1):
b[counting[a[i]]] = a[i]
counting[a[i]] -= 1
for i in range(1, n+1):
print(b[i])
카운팅 정렬을 사용했지만 또 메모리 초과가 발생했다.
검색을 해보니 사람들은 카운팅 정렬을 그대로 사용하지만은 않았다. count한다는 개념은 그대로 적용했지만, 누적 합을 사용하지 않고 바로 출력을 하게 한 것 같았다.
이해한 대로 다시 짜보았다.
import sys
n = int(sys.stdin.readline())
counting = [0]*10001
for i in range(n):
input = int(sys.stdin.readline())
counting[input] += 1 # count
for i in range(1, 10001):
if counting[i] != 0:
for j in range(counting[i]):
print(i)