문제

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

제한사항

• 0 <= s.length <= 3 * $10^4$
• s[i] is '(', or ')'.

접근1(시간 초과)

괄호 유효성 검사 문제였습니다. 기본적으로 stack을 이용해 유효성을 검사했지만, 이번엔 유효성 여부 체크가 아닌, 주어진 문자열에서 가장 긴 유효한 문자열 길이를 반환하는 문제였어요.

그래서 저는 모든 부분 문자열을 검사하는 방향으로 전개를 했습니다. 시간 복잡도는 모든 부분 문자열 $n^2$, 그리고 유효성 검사에서 $n$회 확인하여 $O(n^{3})$을 예상했지만, 밑져야 본전이란 생각으로 했지만 역시나 시간 초과가 발생했습니다.

답안

public class LongestVaildParentheses {
   public int longestValidParentheses(String s) {
        for(int i = 0; i <= s.length() - 2; ++i){
            for(int j = 0; j <= i; ++j){
                if(isValid(s, j, s.length() - 1 - (i - j))){
                    return s.length()- i;
                }
            }
        }

        return 0;
    }

    private static boolean isValid(String s, int start, int end){
        if(start >= end)
            return false;

        Stack<Character> stack = new Stack<>();
        for(int i = start; i <= end; ++i){
            char c = s.charAt(i);
            switch (c){
                case '(':{
                    stack.push('(');
                } break;
                case ')':{
                    if(stack.empty() || stack.peek().compareTo('(') != 0){
                        return false;
                    } else{
                        stack.pop();
                    }
                } break;
            }
        }

        return stack.empty();
    }
}

접근2

유효한 left, right 인덱스를 찾아 두 값의 차를 통해 $O(n)$ 방식을 찾아보려 했으나, 해결하지 못해 답을 보았습니다...

Leet Code에서 제공한 답안 중 가장 빠르고 인상 깊었던 답을 보았는데요,

1. 좌 $\to$ 우 순으로 left와 right 값을 구함
   1-1. 이 과정에서 right가 left보다 같거나 큰 경우 left, right 값을 초기화 $\to$ 우측 괄호가 더 많아져 매칭이 안된 경우
   1-2. left, right 값이 같다면 left + right 값을 현재 최대값과 비교해서 초기화2. 우 $\to$ 좌 순으로 left와 right 값을 구함
   2-1. 이 과정에서 left가 right보다 같거나 큰 경우 left, right 값을 초기화 $\to$ 우측 괄호가 더 많아져 매칭이 안된 경우
   2-2. left, right 값이 같다면 left + right 값을 현재 최대값과 비교해서 초기화

역순으로 한번 더 연산을 수행을 통해 답을 도출하는 부분이 인상 깊었어요. 예전에 어느 기업에서 역순으로 한번 더 전개를 해서 답을 도출하는 문제를 본 적이 있어 익숙해질 필요가 생각되어 전개해봤어요.

아직 미숙해서 다시 풀라고 하면 기억하고 풀 수 있을진 모르겠지만, 이번 기회를 통해 이러한 방식도 있다는 것을 숙지하자는 것에 의의를 두었습니다 ㅎㅎ

답안

public class LongestVaildParentheses {
    public int longestValidParentheses(String s) {
        int ret = 0, left = 0, right = 0;
        // Left
        for(int i = 0; i < s.length(); ++i){
            char c = s.charAt(i);
            if(c == '('){
                left++;
            } else{
                right++;
            }
            if(left == right){
                ret = Math.max(ret, left + right);
            } else if(right >= left){
                left = right = 0;
            }
        }
        // Right
        left = 0; right = 0;
        for(int i = s.length() - 1; i >= 0; --i){
            char c = s.charAt(i);
            if(c == '('){
                left++;
            } else{
                right++;
            }
            if(left == right){
                ret = Math.max(ret, left + right);
            } else if(left >= right){
                left = right = 0;
            }
        }

        return ret;
    }
}