[LeetCode] 32. Longest Valid Parentheses

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

Longest Valid Parentheses - LeetCode

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

'(' 및 ')' 문자만 포함된 문자열이 주어지면, 가장 긴 유효한 괄호 부분 문자열의 길이를 반환합니다.

 

Example 1:

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:

Input: s = ""
Output: 0

Constraints:

0 <= s.length <= 3 * 104
s[i] is '(', or ')'.

 

---

접근방법

1. 사용할 자료구조: stack

괄호가 나와서 바로 stacck자료구조를 떠올렸습니다.

2. 문제 이해

가장 긴 / 유효한 괄호 문자열의 길이를 찾는 것이 문제의 목적입니다.

3. 코드 설계

• 문자열로 되어있는 s를 각각의 문자로 꺼내 쓰기 위해 문자 배열로 바꿉니다.
• 유효한 괄호 문자열의 ‘길이’를 구하기 위해서는 인덱스를 스택에 넣는 게 필요하므로 스택을 선언합니다.
• 유효한 괄호 문자열의 길이를 구해서 넣는 cnt변수, 계속해서 max를 갱신해서 넣을 result변수를 선언합니다.
• stack.push(-1); 를 선언합니다. 
• (가 나오면 stack.push()합니다.
• )가 나오면 stack.pop()을 진행합니다.
  • 스택이 비어있지 않다면, 지금 확인하고 있는 인덱스 - stack.peek()만큼 cnt에 넣고 max를 갱신해서 result에 넣습니다.
  • 스택이 비어있다면 stack.push()합니다.

4. 시간복잡도

주어진 문자열s의 길이를 처음부터 끝까지 돌면 끝나기 때문에 O(N)입니다.

 

5. Test case 추가

Input: s = "(()())"
Output: 6

 

코드 구현

1. 실패 코드

class Solution {
    public int longestValidParentheses(String s) {
        Stack<Character> stack = new Stack<>();
        int cnt = 0;
      
        for(char c : s.toCharArray()) {
            if(c == '('){
                stack.push(c);
            }else if(c == ')'){
                if(stack.peek() == '('){
                    stack.pop();
                    cnt += 2;
                }else{
                    stack.push(c);
                }
            }
        }
        return cnt;
    }
}

실패 코드의 원인

1. 문제 이해를 못함

위의 코드는 유효한 괄호 쌍의 개수를 세지만, 문제의 목적은 가장 긴 유효한 괄호 문자열의 길이를 찾는 것이 문제의 목적입니다.

 

2. Stack이 비어있는 경우의 처리를 하지 않았습니다.

stack.peek()를 호출하기 전에 스택이 비어있는지 확인하는 것이 필요한데, 그렇지 않으면 빈 스택에서 요소를 꺼내려고 할 때 EmptyStackException이 발생할 수 있습니다.

 

2. 성공 코드

import java.util.*;
class Solution {
    public int longestValidParentheses(String s) {

       int result = 0;
       int cnt = 0;
       char[] arr = s.toCharArray();

       Deque<Integer> stack = new ArrayDeque<>();
       stack.push(-1);

       for(int i=0; i<arr.length; i++){
           if(arr[i] == '('){
               stack.push(i);
           }else{
               stack.pop();
               if(!stack.isEmpty()){
                   cnt  = i - stack.peek();
                   result = Math.max(cnt, result);
               }else{
                   stack.push(i);
               }
           }
       }
       return result;
    }
}

 

배우게 된 점

1. Java에서 for-each 문은 어느경우에 사용할 수 있을까? 모든 경우에 다 사용할 수 있을까? NO

모든 컬렉션과 배열에 사용할 수 있습니다. for-each 문은 내부적으로 Iterable 인터페이스를 구현하는 컬렉션에 대해 작동하며, 배열에 대해서도 자동으로 작동합니다.

1. 배열: 모든 종류의 배열(기본 데이터 타입 배열, 객체 배열 등)에 사용할 수 있습니다. int[], String[] 등이 있습니다.
2. 컬렉션: List, Set, Queue 등과 같은 Collection 인터페이스를 구현하는 모든 클래스에서 사용할 수 있습니다. 예를 들어, ArrayList, LinkedList, HashSet, TreeSet 등이 있습니다.
3. Map: 직접적으로는 for-each를 사용할 수 없지만, Map의 keySet(), values(), 또는 entrySet() 메서드를 통해 키, 값, 또는 키-값 쌍을 반복하는 데 for-each를 사용할 수 있습니다.

String에 대해서는 for-each 문을 직접 사용할 수 없습니다. 왜냐하면 String은 Iterable 인터페이스를 구현하지 않기 때문입니다. 그러나 String의 각 문자에 접근하고 싶다면, 먼저 String을 char 배열로 바꾼 후 for-each 문을 사용할 수 있습니다.

String str = "Hello";
for (char c : str.toCharArray()) {
    System.out.print(c);
}

// 출력
Hello

 

 

2. Deque<Integer>를 사용하여 ArrayDeque<>의 인스턴스를 생성함으로써 스택과 큐 모두를 구현할 수 있습니다.

스택(Stack)으로 사용:

스택은 후입선출 구조로 Deque 인터페이스를 사용하여 스택을 구현할 때는 주로 push와 pop 메서드를 사용합니다.

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); 
Integer element = stack.pop();

 

큐(Queue)로 사용:

큐는 선입선출 구조입니다. Deque 인터페이스를 사용하여 큐를 구현할 때는 주로 offer와 poll 메서드를 사용합니다.

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); 
Integer element = queue.poll();

 

 

 

문제가 이해가 되지 않아서 코드 구현 하는 데 까지 하루정도 걸렸습니다. 결국에는 test case 하나하나 넣어가며 이해를 결국에는 했는데, 처음에 list.push(-1)을 어떻게 생각해 냈을까 이런 생각이 들게 하는 문제였습니다...😂