[boj 34031] 하이터치☆메모리

문제 링크

 

괄호 문자열과 관련된 문제.

 

A 괄호열에서 "(" 보다 ")" 가 많아지는 접두사는 사용할 수 없습니다.

B 괄호열에서 접두사가 ")"로 닫히지 않는 접두사도 사용할 수 없습니다.

 

B 괄호열에서 접두사가 ")"로 닫혀야 한다는게 말로 표현하려니까 애매한데, 문제를 직접 풀면서 고민해보신 분은 코드를 보면 금방 이해하실 것 같습니다.

 

import sys
input = sys.stdin.readline


def solve():
    A = input().rstrip()
    B = input().rstrip()
    A_dict = {}
    B_dict = {}
    
    trans = {"(": 1, ")": -1}
    
    cur = 0
    for a in A:
        cur += trans[a]
        if cur < 0: break
        
        A_dict[cur] = A_dict.get(cur, 0) + 1
        
    cur = 0
    tmp = 0
    for b in B:
        cur += trans[b]
        if trans[b] > 0: tmp += 1
        else: tmp = max(0, tmp-1)
        
        if not tmp: B_dict[cur] = B_dict.get(cur, 0) + 1
        
    ans = 0
    for k, v in A_dict.items():
        u = B_dict.get(-k, 0)
        ans += u*v
        
    print(ans)
    
    return


def main():
    solve()
    
    return


if __name__ == "__main__":
    main()