백준 15926번 현욱은 괄호왕이야!!

이것은 2021년 05월 05일

---

주어진 문자열에서 길이가 가장 길면서 올바른 괄호 문자열인 부분 문자열의 길이를 구하는 문제

https://www.acmicpc.net/problem/15926

주어진 문자열이 올바른 괄호 문자열인지 판단하는 문제만 풀다가 이런 문제를 접하니 비슷하겠거니 했다.

그냥 별 생각 없이 올바른 괄호 문자열이면 카운트하고 짝 안맞으면 끊고 새로 카운트하고 이랬다가 당연히 바로 틀렸다. 역시 골드4가 이렇게 단순할리 없지

한참의 시도 끝에 찾아낸 해결책

스택에 괄호만 넣는 것이 아니라 올바른 괄호 문자열의 길이도 함께 넣는다

정리해보면

괄호 문자열을 스택에 하나씩 넣는다

() 짝이 만들어 지면 꺼내고 2를 넣는다

스택에 숫자가 연속으로 있으면 더해서 다시 넣는다

괄호가 들어가야 하는데 숫자가 있으면 숫자를 꺼내고 괄호랑 짝을 맞춰보고 넣을지 꺼낼지 결정한다
예를 들어 스택에 ['(', 4] 이렇게 들어있는데 ) 가 들어올 차례면
4를 일단 꺼내고 (와 )는 짝이 맞으니까 꺼내서 2와 4를 더하고 다시 넣어준다
만약 [')', 4] 였고 )가 들어올 차례였다면 4를 꺼내고 )랑 )는 짝이 아니므로 다시 4를 넣고 )를 넣는다

from collections import deque
from sys import stdin

n = int(stdin.readline())
string = stdin.readline().rstrip()

s = deque()
temp = 0

for i in string:
  if len(s)==0:
    s.append(i)
  elif s[-1] == '(':
    if i == '(':
      s.append(i)
    elif i == ')':
      s.pop()
      s.append(2)
      while str(s[-1]) not in '()':
        temp = temp + s.pop()
        if len(s)==0:
          break
      s.append(temp)
      temp = 0
  elif s[-1] == ')':
    s.append(i)
  else:
    while str(s[-1]) not in '()':
      temp = temp + s.pop()
      if len(s)==0:
        break
    if len(s)==0:
      s.append(temp)
      temp = 0
      s.append(i)
    else:
      if s[-1] == '(':
        if i == ')':
          s.pop()
          temp = temp + 2
          s.append(temp)
          temp = 0
        else:
          s.append(temp)
          temp=0
          s.append(i)
      else:
        s.append(temp)
        temp=0
        s.append(i)
    
ans = 0
for i in s:
  if str(i) not in '()' and i > ans:
    ans = i

print(ans)

시도해본 예제들

5 (())(
14 (()))()((()))(
9 ()()((())
11 ()()((())()
6 ((()))

코드가 사실 생각나는대로 막 적다보니 굉장히 정신없는데

나중에 시간나면 정리해야겠다 ^^