글 읽기 - 최대문자열붙이기 메모리초과...

jhjh9501 4년 전 0

dynamic programming dp에서 메모리초과가 나는거같아서 dp를 아래와 같이 바꾸어줬는데도 메모리초과...

어디서메모리가 터지는지도모르곘ㅅ브니다 ㅜㅠㅠ

import sys
import collections


s = sys.stdin.readline().replace('\n', '')
or_len = len(s)
n = int(sys.stdin.readline())
str_len = [0]*n
match_pos = [[] for _ in range(n)]
#match_str = [[] for _ in range(or_len)]
for l in range(n):
    w = sys.stdin.readline().replace('\n', '')
    m = len(w)
    str_len[l] = m
    fail = [0]*m
    j = 0
    for i in range(1, m):
        while j>0 and w[i]!=w[j]:
            j = fail[j-1]
        if w[i] == w[j]:
            j += 1
            fail[i] = j
    j = 0
    for i in range(0, or_len):
        while j>0 and s[i]!=w[j]:
            j = fail[j-1]
        if s[i]==w[j]:
            if j == m-1:
                match_pos[l].append(i-m+1)
                #match_str[i-m+1].append(l)
                j = fail[j]
            else:
                j += 1
# dp = [-1]*(or_len+1)
# dp[or_len] = 0
# for pos in range(or_len-1, -1, -1):
#     tmp_result = dp[pos+1]
#     arr = []
#     # for k in range(n):
#     #     if pos in match_pos[k]:
#     #         arr.append(k)
#     # for short_str in arr:
#     for short_str in match_str[pos]:
#         if dp[pos+str_len[short_str]]+str_len[short_str] > tmp_result:
#             tmp_result = dp[pos+str_len[short_str]]+str_len[short_str]
#     dp[pos] = tmp_result
# print(dp[0])

MAX_SIZE = 10000
dp = collections.deque([-1]*(MAX_SIZE+1))
#실제 문자열에서의 커서 위치
pos = or_len
#dp 나열에서 현재 pos에 해당하는 커서의 위치
dp_pos = MAX_SIZE
dp[dp_pos] = 0
#dp가 변형되기 시작해서 pos에 해당하는 dp_pos가 항상 0이면 state = 1
state = 0
#실제 문자열에서 커서가 0에 도달하면 중지
pos -= 1
dp_pos -= 1
while pos>=0:
    #실제 문자열에 해당하는 dp_pos를 먼저 구해줘야함.
    if state == 1:
        dp_pos = 0
    #이건 기본 세팅이고
    tmp_result = dp[dp_pos+1]
    arr = []
    #현재 실제 문자열 포지션에서 일치하는 짧은 문자열들의 index 추출
    for k in range(n):
        if pos in match_pos[k]:
            arr.append(k)
    #각 index에서 비교를 해야하는데
    #dp_pos가 0일떄....문제가 없어야하는데 흠
    for short_str in arr:
        if dp[dp_pos+str_len[short_str]]+str_len[short_str] > tmp_result:
            tmp_result = dp[dp_pos+str_len[short_str]]+str_len[short_str]
    dp[dp_pos] = tmp_result
    #print(pos, dp_pos, dp)
    pos -= 1
    if state == 1:
        dp.pop() #마지막 정보는 더이상 사용될 수 없음 문자열 최대 길이 문제로
        dp.appendleft(-1) #dp[0]자리에 -1 값을 추가함. 다음에 업데이트 될 예정
    #dp_pos가 양수면 dp_pos는 감소할수있음
    if dp_pos >0:
        dp_pos -= 1
        #근데 감소시켰는데 dp_pos가 0이 되면 다음부터는 dp_pos는 0으로 유지하고 index 를 바꿔서 업뎃해야함
        if dp_pos ==0:
            state = 1

if dp[dp_pos] != -1:
    print(dp[dp_pos])
else:
    print(dp[dp_pos+1])

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

문제

문제

출처

ICPC

최대문자열붙이기 메모리초과...

jhjh9501 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말