[코드 풀이] 20. Valid Parentheses

문제 파악

20. Valid Parentheses

1. 올바른 괄호를 구해야 한다.
2. 괄호는 소, 중, 대 괄호 다 가능하다.
3. 괄호는 같은 종류의 괄호로 열리고 닫혀야 한다.
4. 괄호 안의 괄호가 열린 후 닫히지 않은 채로 존재하면 안 된다.
5. 괄호가 올바른지 올바르지 않은 지를 true와 false로 판단하여 return한다.

예시
( )⇒ 올바른 괄호
( [ ] ) ⇒ 올바른 괄호
( [ ) ] ⇒ 올바르지 않은 괄호

접근 방법

1. 앞에 열린 괄호가 없는 상태에서 닫힌 괄호가 들어오는 경우에 false를 return 해야 한다.
2. 올바른 괄호 내부에 있는 괄호가 올바르지 않은 경우 false 를 return 한다.
3. 괄호 한 쌍이 서로 다른 종류로 이루어져 있는 경우 false를 return 한다.
4. 이 외의 경우 전부 true 를 return 한다.

실패한 풀이

각 괄호의 종류 별로 open 과 close 를 판단할 boolean 타입 변수를 선언한다.
→ 기본 값은 true로 한다.

괄호가 열리면 false 를 삽입한다.
괄호가 닫히면 true 를 삽입한다.
→ 괄호가 닫힌 경우 다른 종류의 괄호 변수 값을 확인한다.
→ 다른 종류의 괄호 변수가 전부 true 가 아니라면, 즉시 false 를 return 한다.
→ 다른 종류의 괄호 변수가 전부 true 이면 계속 탐색을 진행한다.

탐색이 끝난 후에 모든 괄호 변수가 true 이면 true 를 return 한다.
더 생각을 해봤지만 위의 방법으로는 괄호 내부의 괄호를 판단할 수 없을 것 같다.
다른 방법이 떠오르지 않아 답안을 보기로 했다.

아래는 실패한 코드이다. 괄호 내부의 괄호에서 판단이 되지 않아 실패했다.

class Solution {
    public boolean isValid(String s) {
        boolean bigBracket = false, midBracket = false, smallBracket = false;
        int bigCount = 0, midCount = 0, smallCount = 0;

        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '[' || s.charAt(i) == ']') {
                bigCount += s.charAt(i) == '[' ? 1 : -1;
            } else if(s.charAt(i) == '{' || s.charAt(i) == '}') {
                midCount += s.charAt(i) == '{' ? 1 : -1;
            } else {
                smallCount += s.charAt(i) == '(' ? 1 : -1;
            }
        }

        bigBracket = bigCount == 0 ? true : false;
        midBracket = midCount == 0 ? true : false;
        smallBracket = smallCount == 0 ? true : false;

        return bigBracket == true && midBracket == true && smallBracket == true ? true : false;
    }
}

답안 확인한 후 적용한 풀이

답안은 Stack을 사용했다.

열린 괄호를 만나면, 스택에 해당 괄호와 같은 종류의 닫힌 괄호를 저장한다.

닫힌 괄호를 만나면, 가장 최근에 스택에 저장한 값을 반환하여 비교한다.
→ 같으면 삭제하고, 다르면 false 를 return 한다.

마지막에는 isEmpty() 를 사용하여 비어 있으면 성공적으로 탐색을 마친 것이므로 true 를 반환하도록 한다.

코드 구현

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

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

        return stack.isEmpty();
    }
}

배우게 된 점

Stack을 응용하는 법을 알게 되었다.