[Dyanmic Programming][Hard] 32. Longest Valid Parentheses

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

 

Q. 주어진 string s 에서 (와 )의 parentheses 쌍이 맞는 최대 길이를 찾아라. 

 

 

Solution. 

 직관적으로 우선 생각해 본다. 

 한 string에서 시작점을 기준으로 어디까지 parentheses정의를 만족하나 확인한다. 

 그리고 그 최대 길이를 udpate 한다. 

 도중에 만족하지 않으면, 그 다음 index의 시작점에서 다시 체크를 시작한다. 

 

    int longestValidParentheses(string s) 
    {
        int maxLen = 0;
        int idxStart = -1;
        queue<char> qBuff;
        for (int k = 0; k < s.size(); ++k)
        {
            bool reset = false;
            if (s[k] == '(')
            {
                if (qBuff.empty() && idxStart < 0)
                    idxStart = k;
                qBuff.push(s[k]);
                if (k == s.size() - 1)
                    reset = true;
            }
            else     // ')'
            {
                if (!qBuff.empty())
                {
                    qBuff.pop();
                    if (qBuff.empty())
                        maxLen = idxStart >= 0 ? max(maxLen, k - idxStart + 1) : maxLen;
                    else if (k == s.size() - 1)
                        reset = true;
                }
                else reset = true;
            }
            if (reset && idxStart >= 0)
            {
                k = idxStart;
                while (!qBuff.empty()) qBuff.pop();
                idxStart = -1;
            }
        }
        return maxLen;
    }

 

restart 포지션을 자주 재 정의 해 주어야 하므로, 코드가 다소 복잡해 졌다. 

TC가 최악의 경우 O(N^2) 가 될수 있고, 

아래 결과에서 보듯이 범위를 벗어난 시간이 소요 됐다. 

 

 

다시 생각해 본다. 

한번 s string을 순회하면서 바로 그 길이를 기억하고 update 할수 있는 방법을 찾아 본다. 

즉, parentheses 를 만족하는 구간을 모두 날리고, 만족하지 않는 첫 지점의 index를 기억해서 현재 위치에서 빼면 그것이 만족했던 길이가 된다. 

다만 첫 위치는 0 index의 직전인 -1로 할 필요가 있다. 

 

    int longestValidParentheses(string s) 
    {
        int maxLen = 0;
        stack<int> qBuff;
        qBuff.push(-1);
        for (int k = 0; k < s.size(); ++k)
        {
            if (s[k] == '(')		qBuff.push(k);
            else
            {
                qBuff.pop();
                if (qBuff.empty())
                    qBuff.push(k);
                else
                    maxLen = max(maxLen, k - qBuff.top());
            }

        }
        return maxLen;
    }

만족하는 구간은 pop 하여 날리고, 

그 직전 stack의 top index를 현재에서 빼서 길이를 구한다. 

만약 stack이 비었다면?

만족하지 않는 상황이므로, index로 다시 stack을 채우기 시작한다. 

 

적절한 결과를 얻었다.

 

 

 

Note 1) 훈련에 의해 idea를 얻는 다면 어렵지 않는 문제다. 

 

Note 2) parentheses 관련 문제는 빈번한 문제 중의 하나다. 

 구성하는 방법은 BT, 최대 길이는 지금처럼 DP, 가급적 풀이 패턴을 기억해 두도록 하자.