[백준] 10989 - 수 정렬하기 3

백준 10989번

<정답 코드>

import sys

n = int(sys.stdin.readline().strip())
a = [0] * 10001

for i in range(n):
    a[int(sys.stdin.readline().strip())] += 1

for i in range(len(a)):
    if a[i]:
        for j in range(a[i]):
            print(i)

<처음에 틀린 코드>

import sys

n = int(sys.stdin.readline().strip())
a = []
for _ in range(n):
    a.append(int(sys.stdin.readline().strip()))

a.sort()
for i in a:
    print(i)

문제 설명

이 문제는 메모리 제한이 8MB라 기존에 하던 방식으로 동적할당 방식으로 하게 되면
N(1 ≤ N ≤ 10,000,000)의 조건에 따라 천만개를 수가 필요할 때 마다 한칸 씩 추가하게 되면 메모리를 초과하게 된다. 따라서 미리 개수만큼의 인덱스를 가지고 배열을 만들어주고 +1을 하게 되면 메모리에는 아무런 영향이 없기 때문에 통과하게 된다.
위 첫번째 코드와 같은 방법과 딕셔너리를 이용해서 이미 있는 키값(인덱스)이면 +1을 해주고 없는 키값이라면 추가하는 동적할당(두번째 방식)과 첫번째 방식(인덱스를 가지고 푼 첫번째 코드)를 섞은 방법이 있다.