수 정렬하기 3

내가 작성한 코드

전략 : 인덱스를 수로 생각하고 값에 해당 수가 몇번 들어왔는지 마킹용으로 사용하자!!

import sys
input = sys.stdin.readline
N = int(input())

# 10000과 같거나 작은 자연수
# 0을 자연수로 처리할 수 있으므로 10001까지 하여 0부터 10000까지 처리할 수 있도록 하였다.
arr = [0] * 10001
for i in range(N):
    num = int(input())
    arr[num] += 1
for a in range(len(arr)):
    if arr[a] != 0:
        for i in range(arr[a]):
            print(a)

느낀점

• 직접 수를 정렬하여 메모리에 담은 것은 아니지만, 정렬된 것과 유사하게 사용할 수 있는 방식을 알게되어 즐겁다.

내가 실패한 코드

import sys
input = sys.stdin.readline
N = int(input())
arr = []
for i in range(N):
    arr.append(int(input()))
arr.sort()
for i in arr:
    print(i)

메모리 초과로 실패하였다.. 그 이유로 생각한것이 sort를 할때 기본 퀵 정렬로 구현되어 있는것으로 알고있어 내부에서 재귀적으로 함수를 호출하며 많은 메모리를 사용하게 된다고 생각하였다. 그리하여 sort를 사용하지 않고 입력 받은 수를 정렬하는 방법을 찾았다.
또한 append를 사용하면 메모리 재할당이 이루어 져서 메모리를 효율적으로 사용하지 못한다고 한다.

결과

결과를 보고 드는 생각

문제에서 주어진 메모리 제한은 8MB였는데 사진에는 약 30MB정도로 확인된다. 측정 방식이 어떻게 되는지 의아하다.
이전 문제에서 제출한 코드의 메모리가 76MB인것을 감안한다면 상당히 많은 메모리를 절약한 것은 맞는 것 같다.