글 읽기 - pypy3 메모리 초과 질문.

chlghksdyd24 1년 전 0

안녕하세요, 이 문제를 풀다가 궁금한 점이 생겨서 질문을 남깁니다.

해당 코드를 python3로 제출하면 맞았습니다가 뜨는데 pypy3로 제출을 하면 메모리 초과가 나오더군요.

물론 pypy3가 python3보다 자주 쓰이는 코드를 메모리에 저장한다고 해서, 시간이 더 빠르고 메모리가 더 크게 나오는 건 알지만,

이 부분을 제외해도 제가 짠 코드에 문제가 있어서 메모리 초과가 뜨는 거 같은데 그 이유를 모르겠습니다.

답변 주시면 정말 감사하겠습니다.

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

t = int(input())

def find_parent(x): 
    if x == parent_dct[x]:
        return x
    else:
        parent_dct[x] = find_parent(parent_dct[x])
        return parent_dct[x]

def union(x,y):
    global union_cnt
    global parent_dct
    try:                        # 딕셔너리에 없을 수 도 있으니, 딕셔너리 조회전에 없으면 생성.
        a = parent_dct[x]
    except:
        parent_dct[x] = x
        union_cnt[x] = 1
    try:
        b = parent_dct[y]
    except:
        parent_dct[y] = y
        union_cnt[y] = 1

    x_p = find_parent(x)        # 부모 찾기
    y_p = find_parent(y)

    if x_p != y_p:  # 같은 집합이 아니라면
        if union_cnt[x_p]>=union_cnt[y_p]:      # 집합 크기를 비교해 하나의 집합으로 합병
            parent_dct[y_p] = parent_dct[x_p]
            union_cnt[x_p] += union_cnt[y_p]
            return union_cnt[x_p]
        else:
            parent_dct[x_p] = parent_dct[y_p]
            union_cnt[y_p] += union_cnt[x_p]
            return union_cnt[y_p]
    else:       # 같은 집합이면 집합 크기만 돌려준다.
        return union_cnt[x_p]

for _ in range(t):
    n = int(input())
    parent_dct = {}     # 부모를 저장하는 딕셔너리 (key = 사람이름,value = 부모이름)
    union_cnt = {}      # 집합 크기 저장 딕셔너리 (key = 사람이름,value = 그 사람이 속한 집합의 크기)

    for i in range(n):
        x,y = input().split()
        print(union(x,y))

djm03178 1년 전 1

PyPy3에서 sys.setrecursionlimit은 해당하는 수만큼의 재귀를 수행할 수 있을 정도로 넉넉한 크기의 메모리를 미리 할당받아 놓는 역할을 합니다.

100만 번의 재귀를 위해서 필요하다고 예측하는 메모리가 아주 크기 때문에 메모리 초과가 됩니다.

이 문제에서 재귀는 10만 번 정도까지밖에 들어갈 일이 없으므로 이 크기도 그 정도로 설정해주시면 됩니다.

chlghksdyd24 1년 전 0

와.. 생각지도 못한 곳에 원인이 있었네요.. 가르쳐주셔서 정말 감사합니다. 좋은 하루 되세요!

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

문제

문제

출처

ICPC

pypy3 메모리 초과 질문.

chlghksdyd24 1년 전 0

djm03178 1년 전 1

chlghksdyd24 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말