[LeatCode] Hard 32 Longest Valid Parentheses (Java)

문제 링크

https://leetcode.com/problems/longest-valid-parentheses/description/

풀이

1. 접근 방법

가장 긴 유효한 괄호의 길이를 구하는 문제
괄호 유효성 검사 과정이 필요하기 때문에 스택을 사용

아이디어

• 스택에 유효하지 않은 괄호의 기준이 되는 인덱스 -1을 미리 저장
• 문자열을 순회하면서
  • 열린 괄호 ( 가 나오면 현재 인덱스를 스택에 저장
  • 닫는 괄호 ) 가 나오면 스택에서 값을 꺼내고
    • 스택이 비어 있지 않으면, 현재 인덱스와 스택의 가장 위 인덱스의 차이를 구해 최댓값 갱신
    • 스택이 비어 있으면, 현재 인덱스를 스택에 추가 (유효하지 않은 괄호 기준 초기화)

2. 의사 코드

1. 스택을 초기화하고, 기준점으로 -1을 스택에 추가  
   stack = [-1]  

2. answer(최댓값)을 0으로 초기화  
   answer = 0  

3. 문자열 s를 처음부터 끝까지 순회하며 i번째 문자를 확인:  
   for i in range(문자열 길이):  
      - 문자가 '('일 경우:  
          stack에 현재 인덱스 i를 추가  
          
      - 문자가 ')'일 경우:  
          스택에서 값을 하나 꺼냄 (pop)  
          
          - 스택이 비어 있지 않다면:  
              현재 인덱스 i에서 스택의 가장 위 인덱스를 뺀 값을 구함  
              answer = max(answer, i - stack의 최상단 값)  
              
          - 만약 스택이 비어 있다면:  
              stack에 현재 인덱스 i를 추가 (유효하지 않은 구간 초기화)  

4. 최댓값 answer를 반환  
   return answer  

3. 시간 복잡도

문자열을 한 번 순회하면서, 각 문자에 대해 상수 시간 연산(push, pop, 최댓값 갱신)을 수행
따라서 전체 시간복잡도는 O(n)

4. 구현

import java.util.Stack;

class Solution {
    public int longestValidParentheses(String s) {

        int answer = 0;

        Stack<Integer> stack = new Stack<>();
        stack.push(-1);

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (!stack.isEmpty()) {
                    answer = Math.max(answer, i - stack.peek());
                } else {
                    stack.push(i);
                }
            }
        }

        return answer;
    }
}