[LeetCode] 32. Longest Valid Parentheses (java)

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

 

 

문제 파악

'('과 ')'만을 포함하고 있는 문자열이 주어졌을 때, 유효한 괄호쌍 중 가장 긴 괄호쌍의 길이를 return하라.

 

 

문제 풀이

• 괄호를 stack에 임시 저장해 두었다가, 짝을 찾은 '('는 stack에서 삭제 후 length 계산

Stack

class Solution {
    public int longestValidParentheses(String s) {
        int longest = 0;  // answer
        Stack<Entry> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (!stack.isEmpty() && stack.peek().c == '(')  {
                    stack.pop();
                    int length = (stack.isEmpty()) ? i + 1 : i - stack.peek().index;
                    longest = Math.max(length, longest);
                }
                else {
                    stack.push(new Entry(s.charAt(i), i));
                }
            }
            else {
                stack.push(new Entry(s.charAt(i), i));
            }
        }

        return longest;
    }

    class Entry {
        char c;
        int index;

        Entry(char c, int index) {
            this.c = c;
            this.index = index;
        }
    }
}

📊 실행 결과

 

 

NOTE

• 데이터를 Stack에 저장해 두었다가, 짝을 찾은 데이터는 Stack에서 삭제 👉 '짝 찾기' 문제는 Stack 활용해해서 데이터 관리하기