[BOJ / Python] 10989 수 정렬하기 3

문제

백준 10989 수 정렬하기 3

코드

1. 틀린 코드 -- 메모리 초과

import sys

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

nums.sort()

for x in nums:
    print(x)

백준 2751 수 정렬하기 2에서와 같이 메모리를 줄이기 위해 우선input() 대신 sys.stdin.readline() 을 사용했다.

하지만 이는 메모리 초과를 해결하기엔 부족한 대안이었고, 메모리를 더욱 효과적으로 쓸 수 있는 방법을 생각해야 했다.

2. 맞는 코드

import sys

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

for _ in range(n):
    index = int(sys.stdin.readline())
    nums[index] += 1

for i in range(10001):
    if nums[i] != 0:
        for j in range(nums[i]):
            print(i)

💡 계수 정렬을 이용할 것

메모리를 효과적으로 이용하기 위한 효과적인 코드의 핵심은 계수 정렬을 사용하는 것이다.
기존 2750, 2751 문제에서는 비어있는 리스트를 선언해놓고 append()를 사용하여 입력값을 하나씩 넣어주는 방식을 이용했다.

하지만, ① 이 과정에서 너무 많은 메모리를 소비하고, ② 중복값을 다룰 수 없게 되므로 계수정렬을 이용하였다.

입력값 N이 10000보다 작거나 같은 자연수라고 하였으므로 0을 값으로 가진 10001개의 리스트를 선언한다. 여기서 10000개가 아닌 10001개를 선언한 이유는 인덱스의 값과 실제 입력값을 일치시키기 위해서이다.

입력값이 들어오면 입력값을 인덱스로 하는 리스트의 값을 하나 올려준다. 리스트에 들어있는 수만큼 인덱스와 일치하는 값이 들어온 것으로 이해하면 된다.

nums[3] = 5 라면 입력값 3이 다섯 번 들어온 것

10001개의 리스트 값을 검사하여 그 값이 0이 아닌 리스트들에 대해서 리스트에 들어있는 수만큼 인덱스와 일치하는 값을 출력한다.

[참고자료] 계수 정렬

+)
다만 궁금한 점은 왜 Pypy3로 했을 땐 메모리 초과가 나오고 Python3로 돌렸을 땐 성공이라고 뜰까...?....