가장 긴 연속하는 올바른 괄호 부분 문자열의 길이 구하는 알고리즘

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

 

괄호로만 이루어진 문자열이 주어질때 연속하는 부분 문자열 중 가장 긴 올바른 괄호 문자열의 길이를 구하는 문제

 

-------------------------------------------------------------------------------------------------------------------------------------------------------

 

올바른 괄호 문자열을 구하는 알고리즘은 스택을 이용해서 

 

스택이 비어있는데 (이 들어오면 넣고

 

스택이 비어있지 않을때, (이 들어오는 경우, 스택의 마지막 문자가 (인 경우에는 (이 들어올 수 있고

 

)이 들어오는 경우, 스택의 마지막 문자가 (인 경우에는 제거하고

 

마지막에 스택이 비면 올바른 괄호 문자열이 되는 그런 알고리즘인데

 

https://deepdata.tistory.com/38

stack 활용법 - 올바른 괄호 문자열 판별

 

 

이번엔 부분 문자열중 가장 긴 올바른 괄호 문자열의 길이를 구해야한다

 

이럴때는 스택에는 인덱스를 넣는다

 

1) 초기에는 [-1]로 시작

 

2) 들어오는 문자가 (이면 현재 인덱스를 스택에 넣는다

 

3) 들어오는 문자가 )이면 스택에서 인덱스를 빼고, 스택이 비어있지 않다면,

 

(현재 문자의 인덱스 - 스택의 마지막 위치의 인덱스)가 올바른 괄호 부분 문자열의 길이가 되므로 최댓값을 갱신

 

4) 스택이 비어있다면, 더이상 올바른 괄호 문자열이 되지 않으므로 현재 인덱스를 넣어준다

 

예를 들어 s = ')()()'이라고 하자

 

처음에 [-1]

 

먼저 )이 들어오는데, 스택에서 하나 빼면 [], 비어있으므로 현재 인덱스를 넣는다 [0]

 

(이 들어오면 일단 스택에 넣는다 [0,1]

 

)이 들어오면 스택에서 하나 빼고 [0], 현재 인덱스 2 - 스택의 마지막 인덱스 0 = 2는 현재 괄호 문자열의 길이 () 2이다

 

그리고 (이 들어오면 [0,3]

 

그리고 )이 들어오면 하나 빼고 [0], 현재 인덱스 4에서 스택의 마지막 인덱스 0을 빼면 4-0 = 4가 가장 긴 괄호 문자열 ()()이다

 

스택에 들어가는 인덱스가 올바른 괄호문자열의 인덱스-1이 들어가니까 되는듯?

 

n = int(input())

A = list(input())

stack = [-1]

answer = 0

for i in range(n):
    
    if A[i] == '(':
        
        stack.append(i)
    
    else:
        
        s = stack.pop()

        if len(stack) == 0:
            
            stack.append(i)
        
        else:
            
            if answer < i-stack[-1]:
                
                answer = i-stack[-1]

print(answer)