글 읽기 - 파이썬, 메모리 어떻게 줄이나요

jonghp1128 1년 전 1

알고리즘 분류가 우선순위 큐에 포함 되어 있어서 힙으로 풀려고 여러 번 시도했는데 자꾸만 메모리 초과가 나옵니다.

list의 메모리가 너무 크게 차지하고 있는 것 같아서 heap의 길이가 n보다 크면 heapq.heappop(heap) 코드로 heap 리스트를 조절하려 했습니다. 그런데 이러면 제대로 n번째 큰 수가 나오지 않더라구요.

결국 정렬과 슬라이싱으로 문제를 풀었는데 힙으로 어떻게 메모리를 줄이면 좋을지 잘 모르겠습니다.

import heapq
heap = []
n = int(input())
for _ in range(n):
    for elem in list(map(int, input().split())):
        heapq.heappush(heap, -elem)

for i in range(n):
    if i == n-1:
        print(-heapq.heappop(heap))
    else:
        heapq.heappop(heap)

djm03178 1년 전 0

"list의 메모리가 너무 크게 차지하고 있는 것 같아서 heap의 길이가 n보다 크면 heapq.heappop(heap) 코드로 heap 리스트를 조절하려 했습니다."

이렇게 하면 됩니다. 안 된 코드를 올려주세요.

jonghp1128 1년 전 0

해결했습니다. 감사합니다.

메모리 초과는 n으로 두지 않고 2**n으로 둬서 메모리 초과가 났었고, 틀렸습니다는 코드를 잘못 짜서 n번째 큰 수가 아니라 가장 큰 수를 출력하고 있었어요.

아래는 그 코드입니다.

# 1. 메모리초과&&틀린 코드
import heapq
heap = []
n = int(input())
for _ in range(n):
    for elem in list(map(int, input().split())):
        heapq.heappush(heap, elem)
        if len(heap) > 2**n:
            heapq.heappop(heap)
for i in range(n):
    if i == n-1:
        print(heapq.heappush(heap, elem))
    heapq.heappush(heap, elem)
            

# 2. 틀린 코드
import heapq
heap = []
n = int(input())
for _ in range(n):
    for elem in list(map(int, input().split())):
        heapq.heappush(heap, elem)
        if len(heap) > n:
            heapq.heappop(heap)
for i in range(n):
    if i == n-1:
        print(heapq.heappush(heap, elem))
    heapq.heappush(heap, elem)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬, 메모리 어떻게 줄이나요

jonghp1128 1년 전 1

djm03178 1년 전 0

jonghp1128 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말