Valid Parentheses (Stack)

LeetCode의 Queue, Stack 튜토리얼의 두 번째 문제인 Valid Parentheses다. 스택의 대표적인 활용 예제인 괄호 검사 문제인데 학부에서 자료구조 수업 때 스택을 가르칠 때 빼놓지 않고 등장하는 예제다.

Explore - LeetCode

문제에서 요구하는 사항은 다음과 같다.

• 괄호로 이루어진 문자열이 주어진다.

• 해당 문자열의 괄호 쌍이 올바르게 구성되어 있는지 검사하라.

• 괄호는 '(', '{', '[' 세 종류만 주어진다.

• 열린 괄호는 같은 종류의 괄호로만 닫힐 수 있다.

아마 모든 괄호 검사 문제가 이런 종류로 되어있을 것이다. 올바른 괄호란 "()()[][]{}{}"같은 것을 의미하며 올바르지 않은 괄호란 "()(){}{][][]"처럼 괄호의 짝이 맞지 않는 경우를 뜻한다. 이를 검사하는 가장 기본적인 방법은 맨 처음 괄호부터 순차적으로 확인하며 열린 괄호('(', '{', '[') 일 경우 스택에 삽입하고 닫힌 괄호(')', '}', ']') 일 경우 스택에서 꺼내서 맞는 쌍인지 확인하는 것이다.

 

예를 들어 "(((({}))))"가 올바른 괄호로 이루어져 있는지 검사한다고 할 때 열린 괄호('(((({')들은 스택에 삽입한다. 그리고 닫힌 괄호('}))))')를 만났을 때 스택에서 하나씩 빼서 닫힌 괄호('}')와 가장 최근에 삽입한 열린 괄호('{')가 같은 종류의 괄호인지 확인하면 올바른 괄호인지 판단할 수 있는 것이다. 한 쌍의 괄호 사이에는 다른 괄호가 존재하지 않는다는 점을 이용하여 스택으로 괄호의 짝을 판단하는 것이다.

 

이를 반영한 코드는 다음과 같다. 이번 문제는 스택을 구현하는 게 아니라 스택을 응용하는 것이기 때문에 자바의 Stack 클래스를 활용했다.

import java.util.Stack;

class Solution {
    public static boolean isValid(String s) {
        Stack<Character> parentheses = new Stack<Character>();
        char[] characters = s.toCharArray();
        
        
        for(char character: characters) {
            if('(' == character || '{' == character || '[' == character) {
                parentheses.push(character);            
                continue;
            }
            
            
            if(parentheses.empty()){
                return false;
            } else if(')' == character && '(' == parentheses.peek() ||
                      '}' == character && '{' == parentheses.peek() ||
                      ']' == character && '[' == parentheses.peek()) {
                parentheses.pop();
            } else {
                return false;
            }
            
        }
        
        if(parentheses.size() > 0) return false;
        else return true;
    }
}

주어진 괄호 문자열을 한 글자씩 비교하기 위해 toCharArray() 메서드를 활용하여 char 형 변수들이 담긴 배열로 변환한다. 그리고 각 글자마다 열린 괄호일 경우 parentheses 변수, 즉 스택에 삽입하고 닫힌 괄호일 경우 하나씩 꺼내서 맞는 괄호 쌍인지 비교하고 있다. 이때 괄호 쌍이 틀린 게 아니라 "[[[["처럼 그냥 맞는 괄호가 없어서 아직 스택에 열린 괄호가 남아있는 경우 올바르지 않은 괄호로 판단하기 위해 마지막에 스택의 크기를 검사하고 있다.

 

스택의 대표적인 예제인 만큼 어렵지 않게 풀 수 있었다. 오히려 자바의 String과 char 간 변환이나 이런 게 더 까다로워서 시간이 오래 걸렸던 것 같다. 다른 풀이를 보면 char로 변환하지 않고 인덱스와 String의 charAt() 메서드를 활용하여 한 글자씩 꺼내는 방법도 있었는데 괜찮은 것 같다. 하지만 파이썬이었다면 이런 자잘한 것에 신경 쓰지 않고 로직 자체에 집중할 수 있었을 텐데 이럴 땐 정말 자바가 짜증 날 뿐이다.