32 : Longest Valid Parentheses ( leetcode / java )

* 해결 과정

괄호에 관한 문제이기 때문에 스택을 떠올렸고 스택을 이용하기로 생각했습니다. 그래서 저는 '(' 가 나오는 지점에서 검사를 시작하도록 했습니다. 그래서 ')'의 갯수에 따라 다시 변수를 + - 해준다음에, 최종적으로 0이 나오면 통과이고 아니면 종료입니다. 또한 ')'가 훨씬 많아 변수가 음수가 되면 종료입니다. 하지만 이 풀이법은 시간효율이 너무 좋지 않습니다. 먼저 확인해보겠습니다.

 

class Solution {
    
    int answer=0;
    
    public int longestValidParentheses(String s) {
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='(') DFS(s,i,s.length());
        }
        return answer;
    }
    
    public void DFS(String s, int start, int end){
        int num=0;
        int count=0;
        for(int i=start;i<end;i++){
            if(s.charAt(i)=='(') {
                num++;
                count++;    
            }
            if(s.charAt(i)==')'){
                if(num==0) return;
                else {
                    num--;
                    count++;
                }
                if(num==0) {
                    if(count>answer) answer=count;
                }
            }
        }
    }
}

 

 무려 시간복잡도가 아래에서 5%입니다. 아무래도 '('가 나올때마다 검사를 하니 꽤나 불필요한 계산을 많이 하는 거 같습니다. 

 

 

 

그래서 stack에 대한 해결과정을 찾아보았습니다. stack으로도 구할 수 있었습니다. 대시 아래의 흐름을 따라야 합니다. 처음에 stack에 -1을 넣어준다는 것과 stack.pop()이후 다시 stack을 검사한다는 아이디어가 참신합니다.

 

1. 맨 처음 시작 시 -1을 넣고 시작합니다.

2. ')'을 만나면 stack.pop()을 하지만, 한번더 stack을 검사합니다.

 2-1 스택이 비어있으면 마지막 값을 다시 넣습니다.

 2-2 스택이 비어있지 않으면 최대값을 갱신합니다.

 

새롭게 보는 해결문제방법이었습니다. 시간복잡도는 O(N)으로 해결이 가능하며, 상당히 좋은 효율을 보여주었습니다.

public class Solution {

    public int longestValidParentheses(String s) {
        int maxans = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.empty()) {
                    stack.push(i);
                } else {
                    maxans = Math.max(maxans, i - stack.peek());
                }
            }
        }
        return maxans;
    }
}