문제 링크

15770 - QueryreuQ

문제 설명

빈 문자열 S에 대해서

1. S 맨 뒤에 소문자 하나 추가
2. S 맨 뒤에 있는 문자 제거

의 두가지 연산을 할 수 있다. query가 주어졌을때, i번째 문자가 알파벳이면 문자열 S에 1번 연산을, -이면 2번 연산을 한다.
연산을 한 뒤, 문자열 S에 팰린드롬 부분문자열의 개수를 세보자.

문제 풀이

dp를 활용해서 푼다.

query가 queryr인 경우를 생각해보자.
queryr의 펠린드롬 부분 문자열은 query의 부분 문자열 개수 + query에 r이 추가됨으로서 생기는 부분 문자열의 개수 이다.

일반화 시키면,
str1 = str + str[-1]이라고 했을때,
n_pellindrom[str1] 즉, str1의 부분 문자열 개수는 n_pellindrom[str] + str[-1]이 추가돼서 생긴 펠린드롬이다.

def ispellindrom(string):
    # 문자열이 추가됨으로서 펠린드롬이 생기는지 검사
    count = 0
    for i in range(len(string)):
        tmp = string[i:]
        left, right = 0, len(tmp)-1
        flag = True

        while left < right:
            if tmp[left] != tmp[right]:
                flag = False
                break
            left  += 1
            right -= 1 
        if flag == True:
            count += 1
    return count

전체 코드는 다음과 같다.

import sys
from collections import defaultdict
input = sys.stdin.readline

Q = int(input())
query = input().strip()
answer = [0 for _ in range(len(query))]
n_pellindrom = defaultdict()
S = ''

def ispellindrom(string):
    # 문자열이 추가됨으로서 펠린드롬이 생기는지 검사
    count = 0
    for i in range(len(string)):
        tmp = string[i:]
        left, right = 0, len(tmp)-1
        flag = True

        while left < right:
            if tmp[left] != tmp[right]:
                flag = False
                break
            left  += 1
            right -= 1 
        if flag == True:
            count += 1
    return count

        
for i in range(len(query)):
    pre = S
    count = 0
    # 연산하기
    if query[i] == '-':
        # 지우기 연산에는 펠린드롬 계산할 필요 x
        S = S[:-1]
    else:
        tmp = 0
        if S != '':
            tmp = n_pellindrom[S]
        S += query[i]
        n_pellindrom[S] = tmp + ispellindrom(S)
    print(n_pellindrom[S], end=' ')