[LeetCode] 20. Valid Parentheses - Java

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

Valid Parentheses - LeetCode

---

문제

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:

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

---

풀이

풀이 과정

세 종류의 괄호 '()', '{}', '[]' 로 이루어진 문자열이 주어질 때 여는 괄호와 닫는 괄호의 쌍과 순서가 올바르게 되어있는지 판단하는 문제이다.

스택을 이용하여 괄호를 하나씩 넣으면서 비교하는 방법으로 풀이한다.

먼저 주어진 문자열의 길이가 홀수인 경우에는 짝이 맞지 않는 괄호가 생기게 되므로 바로 false를 return 한다.

// 문자열의 길이가 홀수인 경우 남는 괄호가 생기므로  false를 return
if(s.length() % 2 != 0) {
    return false;
}

 

각 여는 괄호와 닫는 괄호가 같은 쌍인지 판단하기위한 map을 선언하고 괄호들의 매칭 정보를 담는다.

// 각 여는 괄호에 매칭되는 닫는 괄호
Map<Character, Character> map = new HashMap<>();
map.put('(', ')');
map.put('[', ']');
map.put('{', '}');

 

문자열의 길이만큼 반복하며 charAt을 통해 괄호를 앞에서부터 하나씩 탐색한다.
여는 괄호인 경우에는 스택에 값을 추가해주고 닫는 괄호인 경우에는 스택의 가장 위의 값과 비교한다.
스택의 사이즈가 0인 경우 닫는 괄호와 매칭되는 여는 괄호가 없는 경우이므로 false를 return 한다.
스택에서 꺼낸 괄호와 매칭되는 값이 현재 닫는 괄호와 일치한다면 스택에서 제거해주고 일치하지 않는다면 역시 닫는 괄호와 매칭되는 여는 괄호가 없는 경우이므로 false를 return한다.

Stack<Character> stack = new Stack<>();
        
// 문자열 길이만큼 반복
for(int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    // 여는 괄호인 경우
    if(c == '(' || c == '{' || c == '[') {
        // 스택에 추가
        stack.push(c);
    }
    // 닫는 괄호인 경우
    else {
        // 스택의 사이즈가 0이면 false를 return
        if(stack.size() == 0) {
            return false;
        }
        // 스택에서 꺼낸 괄호와 매칭되는 값이 현재 괄호와 일치하면 스택에서 제거
        if(map.get(stack.peek()) == c) {
            stack.pop();
        }
        // 스택에서 꺼낸 괄호와 매칭되는 값이 현재 괄호와 일치하지 않는 경우 불완전한 괄호
        else {
            return false;
        }
    }
}

 

모든 탐색이 끝난 후 stack에 남아있는 값이 없다면 모든 괄호가 짝을 이루고 있으므로 Valid Parentheses가 된다.

// 스택에 남아있는 값이 없으면 Valid Parentheses이므로 true를 return
return stack.size() == 0 ? true : false;

---

최종 코드

class Solution {
    public boolean isValid(String s) {
        // 문자열의 길이가 홀수인 경우 남는 괄호가 생기므로  false를 return
        if(s.length() % 2 != 0) {
            return false;
        }

        // 각 여는 괄호에 매칭되는 닫는 괄호
        Map<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');
        
        Stack<Character> stack = new Stack<>();
        
        // 문자열 길이만큼 반복
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 여는 괄호인 경우
            if(c == '(' || c == '{' || c == '[') {
                // 스택에 추가
                stack.push(c);
            }
            // 닫는 괄호인 경우
            else {
                // 스택의 사이즈가 0이면 false를 return
                if(stack.size() == 0) {
                    return false;
                }
                // 스택에서 꺼낸 괄호와 매칭되는 값이 현재 괄호와 일치하면 스택에서 제거
                if(map.get(stack.peek()) == c) {
                    stack.pop();
                }
                // 스택에서 꺼낸 괄호와 매칭되는 값이 현재 괄호와 일치하지 않는 경우 불완전한 괄호
                else {
                    return false;
                }
            }
        }

        // 스택에 남아있는 값이 없으면 Valid Parentheses이므로 true를 return
        return stack.size() == 0 ? true : false;
    }
}

---