LC32. Longest Valid Parentheses

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

  • 역시 괄호는 스택? 으로 풀었는데 생각보다 복잡하게 풀었다.
  • 처음에 단순하게 풀었을때는 ()() 이런 연결된 괄호를 처리하지 못했다.
  • 때문에 배열을 하나 둬서, 각 위차마다 끝나는 유효 괄호의 길이를 저장하게 두어서 풀기는 풀었음.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int> st, val(s.size());
        int ans = 0;
        for(int i = 0; i < s.size(); i++) {
            if(s[i] == ')' && st.size()) {
                val[i] = i - st.back() + 1 + (st.back()-1 >= 0 ? val[st.back()-1] : 0);
                ans = max(ans, val[i]);
                st.pop_back();
            } else if(s[i] == '(') {
                st.push_back(i);
            }
        }
        return ans;
    }
};
  • Solution을 보니까 끝나는 괄호를 굳이 따로 배열로 저장하지 말고, 맨 마지막것만 그냥 스택에 넣어놓으면 끝이었음.
  • 코드 자체도 훨씬 더 심플해짐.. OMG
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestValidParentheses(string s, int ans = 0) {
        vector<int> st = {-1};
        for(int i = 0; i < s.size(); i++) {
            if(s[i] == ')') {
                st.pop_back();
                if (st.size()) ans = max(ans, i-st.back());
                else st.push_back(i);
            } else if(s[i] == '(') {
                st.push_back(i);
            }
        }
        return ans;
    }
};
  • 상수공간만에 푸는 풀이도 있는데 고민해 볼 것