*[백준/파이썬] 10989번 수 정렬하기 3 | 계수 정렬 (Counting Sort) | 메모리초과 주의

 

 

[메모리 초과]

import sys
n = int(sys.stdin.readline())

nums = [int(sys.stdin.readline()) for _ in range(n)]
nums.sort()
sys.stdout.write('\n'.join(map(str, nums)) + '\n')

 

메모리 초과가 난 이유는 바로 N의 크기가 너무 크기 때문입니다.

• nums = [int(sys.stdin.readline()) for _ in range(n)] 이 코드는 1,000만 개의 정수를 모두 파이썬 리스트에 저장합니다.
• 파이썬에서 정수 객체 1,000만 개를 메모리에 올리면 약 400MB 이상의 메모리를 차지하게 됩니다. 이 문제의 메모리 제한(보통 256MB 또는 512MB)을 초과하거나 아슬아슬하게 걸리게 됩니다.

🛠 10989번의 정석 풀이: 계수 정렬 (Counting Sort)

이 문제는 값의 범위가 10,000으로 매우 작다는 점을 이용해야 합니다. 1,000만 개의 데이터를 저장하는 대신, 값이 몇 번 나왔는지 횟수만 세어서 메모리 사용량을 획기적으로 줄여야 합니다. 이 방법을 **계수 정렬(Counting Sort)**이라고 합니다.

1. 계수 정렬의 핵심 아이디어

1. 크기가 10,001인 배열 (인덱스 0~10000)을 준비합니다.
2. 입력받는 숫자를 리스트에 저장하지 않고, 해당 숫자에 해당하는 인덱스의 카운트(횟수)만 1씩 증가시킵니다.
3. 입력을 모두 받은 후, 이 카운트 배열을 처음부터 끝까지 순회하면서 카운트된 횟수만큼 숫자를 출력합니다.

↓ ↓ ↓ ↓ 

 

[또 메모리 초과]

import sys
n = int(sys.stdin.readline())

# 카운트 배열 인덱스 0부터 10000까지 총 10001개의 공간
counts = [0] * 10001

# 모든 입력값을 리스트에 저장하지 않고, 해당 값의 인덱스에 횟수만 기록
for i in range(n):
    num = int(sys.stdin.readline())
    counts[num] += 1

# 결과 출력
output = []
for i in range(n):
    if counts[i] > 0:
        # 숫자 i를 count[i]번 반복한 문자열을 만들어서 output 리스트에 추가
        # '\n'을 count[i]번 반복하고 마지막에 문자열 i를 붙이는 방식으로 최적화
        output.append((str(i) + '\n') * counts[i])

sys.stdout.write(''.join(output))

 

🛑 메모리 초과 발생 원인 (코드 수정 필요)

잘못된 부분: 출력 반복문의 범위

# ------------------ 🚨 여기가 문제입니다! 🚨 ------------------
for i in range(n):
    if counts[i] > 0:
# -----------------------------------------------------------------
        # ... 출력 로직 ...

• range(n)의 문제: n은 최대 1,000만($10^7$)입니다. 즉, 코드가 counts 배열의 첫 1,000만 개 인덱스를 순회하려고 합니다.
• counts 배열의 실제 크기: counts 배열은 [0] * 10001로, 크기가 10,001밖에 안 됩니다.

결과: $i$가 10,001을 초과하는 순간 (즉, i가 10001이 되는 순간) counts[i]에 접근할 수 없어 IndexError가 발생하거나, 만약 오류가 나지 않더라도 실제 의도와는 완전히 다른 방식으로 작동하게 됩니다.

잠재적인 메모리 문제 (IndexError를 넘어선 상황을 가정했을 때): 만약 n이 10001보다 크다면, 존재하지 않는 배열의 인덱스를 1000만 번 순회하려 시도하므로 불필요한 연산 시간이 발생하거나, 시스템 환경에 따라 메모리 할당 자체가 불안정해질 수 있습니다.

 

 

↓ ↓ ↓ ↓ 

 

[또 메모리 초과]

import sys
n = int(sys.stdin.readline())

# 카운트 배열 인덱스 0부터 10000까지 총 10001개의 공간
counts = [0] * 10001

# 모든 입력값을 리스트에 저장하지 않고, 해당 값의 인덱스에 횟수만 기록
for i in range(n):
    num = int(sys.stdin.readline())
    counts[num] += 1

# 결과 출력
output = []
for i in range(10001):
    if counts[i] > 0:
        # 숫자 i를 count[i]번 반복한 문자열을 만들어서 output 리스트에 추가
        # '\n'을 count[i]번 반복하고 마지막에 문자열 i를 붙이는 방식으로 최적화
        output.append((str(i) + '\n') * counts[i])

sys.stdout.write(''.join(output))

 

🛑 최종 메모리 초과 원인 분석

문제는 output 리스트와 join 과정에 있습니다.

원인: output 리스트에 너무 큰 문자열을 저장

output = []
for i in range(10001):
    if counts[i] > 0:
        # 1. 여기서 문자열을 대량으로 생성하고 (예: "3\n3\n3\n... (1000만 번)")
        # 2. output 리스트에 저장합니다.
        output.append((str(i) + '\n') * counts[i]) 

만약 모든 숫자가 10000이었다면, counts[10000]이 10,000,000이 됩니다. 이 경우, output 리스트에는 ("10000\n" * 10,000,000)이라는 수천만 글자의 거대한 문자열 덩어리가 단 하나의 요소로 저장됩니다.

1. 메모리 낭비: 이 거대한 문자열 자체를 메모리에 생성하는 과정에서 한계치를 초과할 수 있습니다.
2. sys.stdout.write의 한계: 파이썬은 내부적으로 큰 문자열 객체를 다룰 때 메모리 부담이 크며, sys.stdout.write()를 통해 시스템 버퍼에 데이터를 쓰는 가장 좋은 방법은 메모리에 최소한의 데이터만 유지하는 것입니다.

---

 

[메모리 초과를 해결한 최종 코드]

import sys
n = int(sys.stdin.readline())

# 카운트 배열 인덱스 0부터 10000까지 총 10001개의 공간
counts = [0] * 10001

# 모든 입력값을 리스트에 저장하지 않고, 해당 값의 인덱스에 횟수만 기록
for i in range(n):
    num = int(sys.stdin.readline())
    counts[num] += 1

# 결과 출력 (메모리 사용 최소화)
# # output 리스트를 사용하지 않고 바로 출력
for i in range(10001):
    if counts[i] > 0:
        for _ in range(counts[i]):
            sys.stdout.write(str(i) + '\n')

 

- 마지막 줄을 print(i) 로 해도 정답!