단순한 정렬문제이지만 메모리 제한이 있는 케이스

해당 백준 문제는 아래와 같다.

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

메모리에 신경쓰지 않고 그대로 제출하려고 했던 코드는 아래와 같다.

import sys
def LocalInput():
    with open("input.txt") as file:
        datas = file.read().strip().splitlines()
    return datas
def BaekjoonInput():
    datas = sys.stdin.read().strip().splitlines()
    return datas

# datas = LocalInput()[1:]
datas = BaekjoonInput()[1:]

datas.sort()
for data in datas:
    print(data)

인풋 단계에서 메모리를 낭비하지 말자는 아이디어는 있었지만, 어떻게 하면 좋을지 모르겠고 그 외 방도도 떠오르지 않아 GPT에 물어보고, 해당 내용을 학습해보려고 한다.

그 내용은 아래와 같다.

---

메모리를 초과하는 문제는 주로 정렬 시 사용되는 메모리, 데이터 저장 방식, 또는 출력 방식에서 발생할 수 있습니다. 아래에서는 코드의 메모리 사용량을 줄이고 효율적으로 개선할 수 있는 방법을 제시하겠습니다.

문제 분석

• datas = sys.stdin.read().strip().splitlines(): 이 코드는 입력을 한꺼번에 메모리로 읽어와 모든 줄을 리스트로 저장합니다.
• datas.sort(): 정렬 과정에서 추가적인 메모리 사용이 발생할 수 있습니다.
• for data in datas: print(data): 출력할 때도 리스트의 전체 요소를 메모리에 유지한 상태에서 하나씩 출력합니다.

개선 방향

1. 입력 처리 방식 최적화: 한꺼번에 메모리로 읽지 않고, 줄 단위로 읽으며 즉시 처리하는 방식으로 변경합니다. 이렇게 하면 메모리 사용을 줄일 수 있습니다.
2. 정렬을 메모리 효율적으로 수행: 메모리 사용량을 줄이기 위해 외부 정렬(external sorting)처럼 동작하게 만들거나, 파일을 사용하는 방법을 고려할 수 있습니다. 그러나 Python에서는 sorted()를 사용하여 한 줄씩 정렬하는 방식으로도 효과적으로 처리할 수 있습니다.
3. 입력과 정렬을 동시 처리: 입력을 받을 때마다 즉시 처리하여 메모리를 덜 사용하게 합니다.

개선된 코드 예시

import sys
import heapq

def LocalInput():
    with open("input.txt") as file:
        datas = file.read().strip().splitlines()
    return datas

def BaekjoonInput():
    return sys.stdin

# 메모리 초과 방지를 위해 제너레이터를 사용하여 입력 처리
def process_input_and_sort(input_source):
    min_heap = []

    # 첫 번째 줄은 개수 정보이므로 제외하고, 입력을 한 줄씩 처리
    next(input_source)

    # 각 줄을 힙에 추가 (메모리를 효율적으로 사용)
    for line in input_source:
        heapq.heappush(min_heap, line.strip())

    # 힙에서 하나씩 꺼내면서 출력 (정렬된 순서로 출력)
    while min_heap:
        print(heapq.heappop(min_heap))

# main 함수 호출부
# process_input_and_sort(LocalInput())  # 로컬 테스트용
process_input_and_sort(BaekjoonInput())  # 백준 제출용

개선 포인트 설명

1. 제너레이터 사용: 입력을 한꺼번에 메모리에 로드하지 않고, sys.stdin 제너레이터를 사용하여 한 줄씩 읽어 메모리를 절약합니다.
2. 힙 정렬 (heapq) 사용: 메모리 사용량을 줄이기 위해 힙 자료구조를 사용해 점진적으로 정렬된 데이터를 출력합니다. heapq는 파이썬 표준 라이브러리에서 제공하는 힙 자료구조로, 효율적인 메모리 사용과 정렬을 동시에 제공합니다.
3. 지연된 출력 처리: 정렬된 데이터를 즉시 출력하여, 리스트에 모든 데이터를 담고 있지 않도록 합니다.

추가 고려사항

• 파일 기반 정렬: 입력 크기가 매우 클 경우, 파일 기반 외부 정렬(External Sorting) 기법을 사용할 수도 있지만, 이는 보통 경쟁 프로그래밍에서 사용하지 않는 방법입니다.
• Python 버전 및 최적화: 최신 Python 버전에서는 메모리 관리가 조금 더 효율적일 수 있으므로, Python 3.8 이상을 사용하는 것도 고려해볼 만합니다.

이 방법을 사용하면 메모리 사용을 최적화하여 메모리 초과 문제를 해결할 수 있습니다.

---

전체적으로 생소한 내용이라 바로 학습.