[Algorithm][Python] 백준(BOJ) 10989 수 정렬하기 3

[문제]

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

---

[내 코드 - 메모리 초과]

import sys
n = int(input())

arr = []

for _ in range(n):
    arr.append(int(sys.stdin.readline().strip()))

arr.sort()

for i in arr:
    print(i)

📌 주의

• 메모리 제한 - 8MB 이 걸려있다.
• 기본 정렬 라이브러리를 사용하여 풀었는데 메모리 초과가 떴다.
• 메모리 제한으로 모든 입렵 값을 모두 입력 받아 정렬하는 방법은 안된다!
  

💡해결 방법

• 입력 받는 개수는 최대 10,000,000개 인데, 수는 최대 10,000이므로 계수 정렬을 사용한다.
• 10,001(인덱스 1부터 사용)개의 배열을 미리 생성해두고 입력되는 수가 인덱스인 곳의 count를 +1씩 한다.
• 배열 값이 0 개인 곳을 제외하고 배열 인덱스(출력하는 수)를 출력한다.
• 이때, count 개수만큼(배열 값) 출력한다.

# 계수 정렬
import sys

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

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

for i in range(len(arr)):
    if arr[i] != 0:
        for _ in range(arr[i]):
            print(i)

📌 주의
같은 코드인데 메모리 초과가 떠서 알아보니 PyPy3이 Python3보다 시간은 빠르지만 메모리를 더 많이 소모한다고 한다. 메모리 제한이 강할 때는, Python3을 이용해 제출하자!!