Leet code - Longest Valid Parentheses

문제설명

문자열이 주어진다.
괄호 (,) 가 주어지는데 여기서 괄호 정합성이 맞는 문자열의 최대 길이 갯수를 구하여라

해결방법

스택을 이용해서 해결했다.
괄호문제는 일단 대부분 스택을 사용하는데,

여기 같은 경우는 가장긴 괄호 정합성을 찾아야 하기 때문에 꽤나 까다로웠다.

왜냐하면
)(()(( 의 괄호정합성 값은 2이지만
)(()(()))의 괄호정합성 값은 8로 값이 확 늘어난다.

정합성을 체크하는 boolean[s.length()]를 두고,
) 가나올때 현재 위치에서 가장가까운 ( 위치를 찾아서, true를 시켜주는 방식으로 해결했다.

코드

import java.util.*;
import java.lang.*;
class Solution {
    public int longestValidParentheses(String s) {
        Stack<Character> stack = new Stack();
        boolean[] isOk = new boolean[s.length()];
        
        for(int i=0; i<s.length(); i++){
            char c= s.charAt(i);
            if(c=='('){
                stack.push('(');
            }else{
                try{
                    stack.pop();
                    isOk[i] = true;
                    int index = findFalsePos(isOk,i);
                    isOk[index] = true;
                    
                }catch(Exception e){
                    isOk[i] = false;
                }
            }
        }
        
        
        int max = 0;
        int num = 0;
        for(int i=0; i<isOk.length; i++){
            if(isOk[i]) num ++;
            else num = 0;
            if(num>max) max = num;
        }
        
        return max;
    }
    
    public int findFalsePos(boolean[] isOk,int current){
        for(int i=current; i>=0; i--){
            if(!isOk[i]) return i;
        }
        return -1;
    }
}

결과

나같은 경우는 $O(n^2)$의 시간 복잡도가 걸렸다.

해답을 보니 $O(n)$이 가장 최적이고
최악은 $O(n^3)$ (Brute Force를 이용한 경우)였다.

뭔가 아쉬웠다.

DP문제를 풀러왔는데 DP로 안풀어서 그런가보다.