[BOJ] 15926번 현욱은 괄호왕이야!!

[BOJ] 15926번 현욱은 괄호왕이야!! 문제

굉장히 어려웠던 스택 문제다.

올바른 괄호 문자열의 전체 길이를 구하는 것과 그 길이가 얼마만큼 되는 것인지가 중요하다.

import sys

if __name__ == '__main__':
    N = int(sys.stdin.readline().rstrip())
    bracket_str = list(sys.stdin.readline().rstrip())
    max_bracket = 0
    stack = [-1]

    for i in range(N):
        if bracket_str[i] == '(':
            stack.append(i)
        else:
            stack.pop()
            if stack:
                max_bracket = max(max_bracket, i-stack[-1])
            else:
                stack.append(i)

    print(max_bracket)

 

당연하지만 올바른 괄호 문자열은 '(' 이랑 ')' 가 하나의 세트여야 하고, 이런 문제류는 스택이 기본 풀이법이다. $ n=200000 $인데 2초를 주는 이유는 $ O(N) $의 시간복잡도의 트릭을 쓰라는 것이고, 이는 곧 스택을 쓰라고 그런 것이다. 그리고 이걸로 유효한 올바른 괄호 문자열 길이를 얻어내고자 하는 것이 이 문제의 핵심이다. 

문자의 개수만큼 for문을 돌려서 '(' 가 나오면 해당 자리를 의미하는 숫자를 넣고, ')'가 나오면 그때 길이를 구한다.

')' 가 나올 때는 두 가지 상황이 나오는데, 하나는 스택이 빌 때고 다른 하나는 스택이 있을 때다.

stack 변수에 -1을 미리 넣어두고, ')' 를 만난 경우 바로 pop을 한 후에 아래의 작업을 한다.

스택이 있는 경우는 올바른 괄호 문자열의 일부라는 뜻이고, 지금 ')' 와 대응되는 '(' 와의 거리를 계산한다. 이 거리 계산을 위해 -1을 stack에 미리 집어넣는다.

스택이 없는 경우는 유효한 올바른 괄호 문자열이 아니므로 해당 글자의 위치를 넣는다. 이를 위해 pop을 선제적으로 한다.

아래의 예시를 들면서 마무리한다.

# Input
14
(()))()((()))(

 

# Result of stack and max_bracket

[-1], 0
# for loop start
[-1, 0], 0
[-1, 0, 1], 0
[-1, 0], 2
[-1], 4
[4], 4
[4, 5], 4
[4], 4
[4, 7], 4
[4, 7, 8], 4
[4, 7, 8, 9], 4
[4, 7, 8], 4
[4, 7], 4
[4], 8
[13], 8
# for loop end