글 읽기 - 파이썬 dictionary 자료구조의 메모리 사용량

wwiiiii 8년 전 0

모든 문자 방정식을 좌변의 문자열을 key로 사용, 우변의 문자열을 value로 사용해서 dictionary에 다 저장한 뒤에 재귀호출로 방정식의 결과인 문자열을 뽑아내게 짰습니다.

그런데 메모리 초과가 나오네요...key값을 다 해싱해서 구현했을거라 짐작해 메모리 초과가 안날거라 생각했는데, 아무래도 모든 key 객체를 일일이 다 저장하나 봅니다. 어쨌거나 이 구현에서 더이상 메모리를 줄일 방법이 떠오르지 않는데, 다른 방법이 없을까요?

def isBinA(a, b):
    idx = 0
    for i in b:
        while idx < len(a) and a[idx] != i:
            idx+=1
        if idx>=len(a):
            return 0
    return 1
            

def collapse(key, container):
    ans = ""
    if '+' in container[key]:
        for i in container[key].split('+'):
            ans += collapse(i, container)
        container[key] = ans
        return ans
    else:
        return container[key]
    
def task():
    container ={'0':'0'}#dictionary
    k = input()
    for i in range(k):
        temp = raw_input().split()
        equation = ""
        for i in temp:
            if not (i is ' '):
                equation+=i
        left = equation.split('=')[0]
        right = equation.split('=')[1]
        container[left] = right
    T = collapse(raw_input(), container)
    P = raw_input()
    res = isBinA(T,P)
    if res == 0:
        print 'NO'
    else:
        print 'YES'

def main():
    t = input()
    for i in range(t):
        task()

main()

handrake 8년 전 1

숏코딩 가서 파이썬 안 보이면 일단 파이썬으로 불가능하구나 생각하시면 80%는 맞습니다.

wwiiiii 8년 전 0

아무래도 문자열 압축을 일일이 풀어놔서 그런것같네요...기본 단위들의 식으로만 표현하면 될거같은데

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

문제

문제

출처

ICPC

파이썬 dictionary 자료구조의 메모리 사용량

wwiiiii 8년 전 0

handrake 8년 전 1

wwiiiii 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말