[백준/15926] 현욱은 괄호왕이야!! (Python)

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

15926번: 현욱은 괄호왕이야!!

 

Difficulty : Gold 3

 

Status : Solved

 

Time : ??:??:??

 

---

 

문제 설명

 

여는 괄호 ‘(’와 닫는 괄호 ‘)’로 구성된 문자열에서 아래의 조건을 만족하는 문자열을 올바른 괄호 문자열이라고 부른다.

• () 는 올바른 괄호 문자열이다
• 어떤 문자열 x가 올바른 괄호 문자열이라면, (x)도 올바른 괄호 문자열이다.
• 어떤 문자열 x와 y가 올바른 괄호 문자열이라면, xy도 올바른 괄호 문자열이다.

현욱은 친구로부터 생일 선물로 굉장히 긴 괄호 문자열을 받았다(도대체 왜 이런 걸 선물하는걸까?). 하지만 현욱은 올바른 괄호 문자열이 아니면 굉장히 싫어하기 때문에, 받은 괄호 문자열에서 연속한 일부분을 잘라서 올바른 괄호 문자열을 만들려고 한다. 그리고 이왕이면 긴 문자열이 좋으니 현욱은 부분 구간을 최대한 길게 잘라내려고 한다. 현욱을 도와 주어진 괄호 문자열에서 위의 조건을 만족하는 가장 긴 부분 문자열의 길이를 계산하는 프로그램을 작성해보자.

 

입력 및 출력

 

입력

 

첫 줄에 문자열의 길이 n (1 ≤ n ≤ 200,000)이 주어진다.
둘째 줄에 괄호로만 구성된 길이 n짜리 문자열이 주어진다.

 

출력

 

주어진 문자열에서 길이가 가장 길면서 올바른 괄호 문자열인 부분 문자열의 길이를 출력한다. 올바른 괄호 문자열인 부분 문자열을 찾을 수 없는 경우 0을 출력한다.

 

입력 예시

 

5
(())(

 

출력 예시

 

4

 

 

---

 

풀이

 

이중 스택을 사용해보자.

 

우선 괄호를 보관하는 스택을 떠올려보자. 이 스택은 '('가 들어오면 인덱스를 저장하고, ')'가 들어왔을 때 스택에 인덱스가 존재한다면 스택을 pop한다. 이렇게 만들어진 괄호 순서쌍은 [start, end]의 인덱스 범위를 포함하며, 길이는 start + end - 1이다.

 

두 번째로, 정답 후보군 스택을 생각해보자.

• 앞서 괄호를 보관하는 스택에서 pop된 괄호 순서쌍의 start가 정답 후보군 스택의 top의 start보다 작다면, 현재 괄호 순서쌍이 정답 후보군 스택의 top을 포함함을 의미한다. 이를테면, '(())'의 경우 정답 후보군 스택에는 [1, 2]값이 들어있을 것이고, 괄호 순서쌍 [0, 3]값이 들어오게 될 것이다. 즉 두 start를 비교하여 스택의 top을 포함하는 경우를 모두 제거한다.
• 두번째로, 괄호 순서쌍의 start가 정답 후보근 스택의 top의 end와 1차이라면, 두 괄호 순서쌍은 이어질 수 있다. 이를테면 '()()'의 경우, 정답 후보군 스택에는 [0, 1]이, 괄호 순서쌍은 [2, 3]값이 들어올 것이다. 이 경우는 두 범위를 합쳐 새로 정답 후보군 스택에 삽입한다.

최종적으로 정답 후보군 스택에는 올바른 괄호 문자열의 가장 큰 부분집합들이 포함되어 있으며, 이들 중 제일 길이가 긴 괄호 순서쌍의 길이를 출력하면 된다.

 

풀이 코드

N = int(input())
string = input().strip()
stack = []
answers = [[-1, -2]]
for i in range(N) :
  if string[i] == '(' :
    stack.append(i)
  elif stack :
    tmp = [stack.pop(), i]
    while answers and answers[-1][0] > tmp[0] :
      answers.pop()
    if answers and answers[-1][1] + 1 == tmp[0] :
      tmp[0] = answers.pop()[0]
    answers.append(tmp)

answers.sort(key = lambda x : x[1] - x[0])
print(answers[-1][1]-answers[-1][0]+1)

풀이 완료!