[Leetcode] 20. Valid Parentheses.java

1. 문제

문제 설명

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.

제한사항

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

입출력의 예

Example 1:

• Input: s = "()"
• Output: true

Example 2:

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

Example 3:

• Input: s = "(]"
• Output: false

2. 풀이 과정

1. 자료구조 스택을 이용해서 여는 괄호는 저장하고, 닫는 괄호가 나왔을 때 스택에서 꺼내어 매칭되는지 확인한다.
2. 반복문 for문으로 문자열을 순회한다. 각 문자를 하나씩 확인한다.
3. switch문으로 여는 괄호는 스택에 push하고, 닫는 괄호는 pop하여 매칭되는지 확인한다.
4. 문자열을 모두 처리한 후 스택이 비어 있으면 모든 여는 괄호가 올바르게 닫힌 것이므로 true를 반환한다.
5. 스택이 비어 있지 않으면 아직 닫히지 않은 여는 괄호가 남아있으므로 false를 반환한다.

3. 최종 코드

import java.util.Stack;

class Solution {
    public boolean isValid(String s) {
        // 스택 초기화
        Stack<Character> stack = new Stack<>();
        
        // 문자열 순회
        for (char c : s.toCharArray()) {
            switch (c) {
                // 여는 괄호는 스택에 추가
                case '(':
                case '{':
                case '[':
                    stack.push(c);
                    break;
                // 닫는 괄호는 스택에서 pop하여 확인
                case ')':
                    if (stack.isEmpty() || stack.pop() != '(') {
                        return false;
                    }
                    break;
                case '}':
                    if (stack.isEmpty() || stack.pop() != '{') {
                        return false;
                    }
                    break;
                case ']':
                    if (stack.isEmpty() || stack.pop() != '[') {
                        return false;
                    }
                    break;
            }
        }
        
        // 스택이 비어 있으면 모든 괄호가 올바르게 닫힌 것
        return stack.isEmpty();
    }