[스택 (Stack)] LC #20 Valid Parentheses

문제 설명

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Constraints:


문제 링크: https://leetcode.com/problems/valid-parentheses/

1. 문제의 핵심: 스택(Stack)의 LIFO(Last-In, First-Out) 특성 활용

이 문제는 "가장 나중에 들어온 것이 가장 먼저 나간다"는 스택의 LIFO 특성을 활용하는 가장 대표적인 예제입니다. 괄호의 짝을 맞추는 과정을 생각해봅시다. ([{}])와 같은 문자열에서, 가장 안쪽의 {는 가장 먼저 }와 만나 짝을 이루고 사라져야 합니다.

핵심 아이디어: 여는 괄호를 만날 때마다 스택에 저장하고, 닫는 괄호를 만나면 스택의 가장 위(가장 최근에 넣은 여는 괄호)를 꺼내 짝이 맞는지 확인한다.

2. 해결 전략

  1. 문자를 담을 스택을 생성합니다.
  2. 입력 문자열을 한 글자씩 순회합니다.
  3. 현재 문자가 여는 괄호((, {, [)이면 스택에 push합니다.
  4. 현재 문자가 닫는 괄호(), }, ])이면 다음을 검사합니다.
    • 스택이 비어있으면, 짝을 맞출 여는 괄호가 없으므로 false를 반환합니다.
    • 스택에서 pop한 괄호가 현재 닫는 괄호와 짝이 맞지 않으면 false를 반환합니다.
  5. 문자열 순회가 끝난 후, 스택이 비어있으면 모든 괄호의 짝이 맞은 것이므로 true를, 스택에 문자가 남아있으면 짝이 맞지 않은 여는 괄호가 남은 것이므로 false를 반환합니다.

3. Java 코드 구현

import java.util.Stack;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
            } else {
                // 닫는 괄호인데 스택이 비어있거나, 짝이 맞지 않는 경우
                if (stack.isEmpty() || stack.pop() != c) {
                    return false;
                }
            }
        }

        // 모든 순회가 끝난 후 스택이 비어있어야 유효함
        return stack.isEmpty();
    }
}

💡 코드 세부 포인트