LeetCode: 32번 (Longest Valid Parentheses) [JAVA]

문제 링크

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

Longest Valid Parentheses - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 주어진 문자열 s만큼의 길이를 가진 boolean 배열 생성
2. 스택을 통해 전체 s 속 '('와 ')'를 스택에 집어넣거나 조건에 맞는 경우 꺼내며, 조건에 맞는 경우 꺼냄과 동시에 이 문자의 위치에 해당하는 boolean 배열 부분에 true로 삽입
3. 전체 탐색이 끝나면 앞선 boolean배열을 돌며 제일 긴 길이를 계산 후 반환

 문제에서 요구하는 맞는 쌍에 대한 것은 비슷한 문제가 많기에 스택을 사용하여 쉽게 해결할 수 있다. 다만 이 문제에선 좀 더 복잡하게 단순 맞는 쌍들의 개수를 반환하는 것이 아닌 이 쌍들이 이어진 최대 길이를 반환해야 하기에, 쌍을 탐색함과 동시에 이게 어디의 문자인지를 체크할 필요가 있다.

 그렇기에 문자열 s와 동일한 길이의 boolean 배열을 선언 후, 스택을 기반으로 한 탐색을 할 때 해당 문자와 위치를 동시에 담는다. 그렇게 탐색을 진행하며 맞는 쌍이 생길 경우, 알아낸 양쪽 문자의 위치에 맞게 boolean 배열에 true를 삽입한다. 그렇게 탐색을 완료하고 boolean 배열을 처음부터 돌며, true가 연이어 발생한 제일 긴 길이를 찾아 반환하면 된다.

 

class Solution {
    public int longestValidParentheses(String s) {
        int answer = 0, length = 0;
        Stack<Infor> stack = new Stack<>();
        boolean[] isValid = new boolean[s.length()];

        for (int i = 0; i < s.length(); i++) {//전체를 돌며 맞는 쌍 탐색
            Character now = s.charAt(i);

            if (now.equals(')')) {
                if (!stack.isEmpty()) {
                    Infor prev = stack.peek();

                    if (prev.c.equals('(')) {//조건에 부합하면
                        isValid[i] = true;
                        isValid[prev.pos] = true;
                    }

                    stack.pop();
                }
            } else {
                stack.push(new Infor(now, i));
            }
        }

        for (int i = 0; i < isValid.length; i++) {//최장 길이 탐색
            if (!isValid[i]) {
                answer = Math.max(answer, length);
                length = 0;
            } else {
                ++length;
            }
        }
        answer = Math.max(answer, length);

        return answer;
    }

    class Infor {//문자와 해당 위치를 담은 클래스
        Character c;
        int pos;

        public Infor(Character c, int pos) {
            this.c = c;
            this.pos = pos;
        }
    }
}

결과