[LeetCode] 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.

 

Example 1:

Input: s = "()" Output: true

Example 2:

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

Example 3:

Input: s = "(]" Output: false

Example 4:

Input: s = "([)]" Output: false

Example 5:

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

 

Constraints:

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

---

풀이코드

import java.util.*;


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

        for (int i=0; i<s.length(); i++) {
            if (stack.isEmpty()) {
                stack.push(s.charAt(i));
            } else if (stack.peek() == '(' && s.charAt(i) == ')') {
                stack.pop();
            } else if (stack.peek() == '{' && s.charAt(i) == '}') {
                stack.pop();
            } else if (stack.peek() == '[' && s.charAt(i) == ']') {
                stack.pop();
            } else {
                stack.push(s.charAt(i));
            }
        }

        return stack.isEmpty();
    }
}

---

풀이방법

괄호(특수문자)를 주고 여는 괄호와 닫는괄호가 만나면 괄호는 지워지며, 그렇게 지워서 남은 괄호가 없으면 true 남은 괄호가 있으면 false를 return 하는 문제이다.

1. stack을 사용하여 괄호를 저장해주며, 스택이 비어있다면 스택에 비교할 값이 없으므로 받은 괄호를 우선 push해준다.
2. 다음 들어온 괄호를 스택의 마지막 값과 비교하여 짝이 맞는 닫는 괄호인지 확인한다.
3. 닫는 괄호라면 스택의 마지막 값을 지워주면 짝이맞는 두개의 괄호가 사라지게 된다. 
4. 위와같은 조건을 반복적으로 실행하여서 스택의 값이 있는지 여부를 return하게되면 풀이는 종료된다.