[LeetCode - Easy] 20. Valid Parentheses

해석과 풀이는 개인적인 부분이기 때문에 참고만 하시길 바랍니다. 다른 접근 및 풀이는 언제나 환영합니다. 댓글로 남겨주세요.

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.

Example 1:

Input: s = "()"

Output: true

Example 2:

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

Output: true

Example 3:

Input: s = "(]"

Output: false

 

* parenthesis[ pəˈrenθəsɪs ] 삽입어구, bracket (복수형 parenthesises)

* brace[ breɪs ] 버팀대, 대비를 하다, 버팅기다, 중괄호

2. 해석

주어진 문자열에서 괄호 '(' 와 중괄호 '{', 대괄호 '['가 나올 경우 열린 괄호는 동일한 괄호로 닫혀야하고, 닫힐 때 순서가 맞아야 하며, 닫는 괄호에는 동일한 열린 괄호가 있다는 것이다.

모두 올바르게 열고 닫는 짝이 맞을 경우 해당 문자열은 유효하다 true, 아니면 false를 반환한다.

3. 나의 풀이

- 주어진 문자열(s)를 반복문으로 돌리면서 괄호 하나씩 가져오고

- 하나씩 가져온 괄호를 빈 문자열 tmp에 담아둔다.

- 담아둘 때 닫히는 괄호가 등장하면 동일한 열린 괄호가 tmp의 마지막 문자열에 있는지 확인한다.

- 동일한 열린 괄호가 있으면 있으면 tmp에서 마지막 문자열을 제거한다. (즉, (), {}, [] 짝으로 나올 경우 짝을 제거)

- 최종 tmp에 괄호가 남아 있다면 해당 주어진 문자열(s)은 유효하지가 않다.

package leetCode;

class Solution {
    public boolean isValid(String s) {
        boolean rtn = false;
        String tmp = "";
        
        for(int i=0; i<s.length(); i++) {
            char chr = s.charAt(i);
            
            int size = tmp.length();
            if(size == 0) tmp += chr;
            
            if(size > 0) {
                String lastStr = tmp.substring(size-1);
                
                // 닫히는 괄호가 나올경우 tmp의 마지막 문자열을 비교
                if(
                        (chr == ']' && lastStr.equals("[")) ||
                        (chr == '}' && lastStr.equals("{")) ||
                        (chr == ')' && lastStr.equals("("))
                        ) {
                    tmp = tmp.substring(0, size-1);// 마지막 문자열의 열린 괄호를 제거
                }else {
                    tmp += chr;
                }
            }
        }

        if(tmp.length() == 0){
            rtn = true;
        }
        return rtn;
    }
}

 

4. leetCoder의 접근 및 풀이

- Stack의 특성을 사용하여 (언제나 그렇듯 아주) 쉽게 문제를 해결하였다.

- 스택에 대해 짚고 넘어갈 부분은 Stack 클래스의 정리 및 활용을 참고하길 바란다.

- 빈 스택객체를 만들어 열린 괄호가 나오면 이에 매칭되는 닫는 괄호를 담다가(push)

- 닫는 괄호가 나올 경우 바로 직전에 담았던 괄호를 꺼내어(pop) 동일한 닫는 괄호인지 비교하여 아닐 경우 유효한 문자열이 아니라고 반환한다. 끝~

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<Character>();
        for (char c : s.toCharArray()) { // loop
        
            // 열린 괄호에 매칭되는 닫히는 괄호를 스택에 담는다.
            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();
    }
}

- stack.pop()의 경우 if절에서 비교위해 사용되었지만 한 번 해당 함수를 호출하게 되면 일단 스택에서 값을 꺼낸다는 사실을 명심하자!

- 값을 비교하는 것과 스택에서 값을 꺼내어 제거하는 2가지 동작을 한 번에 수행한 참 똑똑하게 코드를 작성한 것 같다.