[Leetcode][C++][난이도 Easy] Valid Parentheses

Leetcode의 난이도 easy 5번째 문제는 valid parentheses 입니다. 입력으로 주어지는 string s에는 오직 소괄호, 중괄호, 대괄호 기호들만 들어 있는데요, 이들이 서로 짝을 이루는 경우라면 true, 짝을 이루지 못하는 경우라면 false를 반환해야 합니다. 우선 문제 분석을 진행하겠습니다. 

 

 

Valid Parentheses 문제 분석

 

[사진 1] Valid Parentheses 문제

 

첫번째 예제에서는 s가 "()" 으로 주어졌네요. 이 경우, "(" 문자가 ")" 와 서로 쌍을 이루기 때문에, 최종 결과는 true가 됩니다. 두번째 예제에서는 s가 "()[]{}" 으로 주어졌습니다. 이 경우도 역시 각각의 "(", "[", "{" 기호가 ")", "]", "}" 기호와 쌍을 이루기 때문에, 역시 최종 결과는 true가 됩니다. 하지만 세번째 예제는 어떨까요? 이 경우에는 "(" 기호가 있으므로, ")"가 있어야 짝을 이루는데, "]"만 있어서 짝을 이룰 수 없습니다. 반대로, "]" 는 "[" 가 있어야 짝을 이루는데 "[" 기호가 없네요. 따라서 false가 반환되어야 합니다. 

 

 

Valid Parentheses 문제 해결을 위한 C++ 코드 

 

#include <stack>

class Solution {
public:
    bool isValid(string s) {
        bool result = true;
        stack<char> par_stack;
        
        if ((s.length() < 2) || ((s[0] == ')') || (s[0] == ']') || (s[0] == '}')))
            return false;
        
        for (int i = 0; i < s.length() ; i++)
        {
            if ((s[i] == '(') || (s[i] == '[') || (s[i] == '{'))
                par_stack.push(s[i]);
            else if (i > 0)
            {
                if (par_stack.empty() && ((s[i] == ')') || (s[i] == '}') || (s[i] == ']')))
                    return false;
                else if ((par_stack.top() == '(') && (s[i] == ')'))
                    par_stack.pop();
                else if ((par_stack.top() == '{') && (s[i] == '}'))
                    par_stack.pop();
                else if ((par_stack.top() == '[') && (s[i] == ']'))
                    par_stack.pop();
                else
                    return false;
            }
        }
        
        if (!par_stack.empty())
            result = false;
        
        return result;
        
    }
};

 

이제 제가 작성한 코드를 살펴보겠습니다. 저는 이 문제를 봤을 때 스택 (stack)이라는 자료구조를 사용하면 쉽게 풀리지 않을까 생각했습니다. 스택에 대한 wikipedia 설명은 이 포스트의 맨 아래 참고 자료에 링크를 걸어두었으니, 한 번 확인해보시기 바랍니다. 첫 조건문에서는 입력받은 string의 길이가 1 이하이거나, 맨 처음 문자가 ), ], } 문자라면 바로 false를 반환하도록 작성했습니다. 만약 string의 길이가 1이하라면, 괄호 문자가 1개 또는 어떤 문자도 없다는 의미이기 때문에, 괄호 쌍을 만들 수 없어서 false가 반환되어야 합니다. 또한, 첫 문자부터 닫힌 괄호 문자들이라면, 이 닫힌 괄호 문자 이전에 열린 괄호 문자가 없다는 의미이므로, 이 역시 괄호 쌍을 만들 수 없습니다. 따라서, 첫번째 괄호 문자들만 검사해봐서, 닫힌 괄호들이라면 바로 false를 반환해주었습니다. 

 

조건문 이후에 string s의 길이만큼 for loop을 돌면서, 열린 괄호가 등장할 때마다 스택에 저장하였습니다. 만약 for loop을 돌면서, 닫힘 괄호를 만나게 되면, 스택의 제일 위에 저장되어 있는 괄호 문자랑 비교해서, 쌍을 이룰 수 있는 괄호 문자라면 스택에서 pop을 수행합니다. 이미 스택을 공부하신 분들이라면 아시겠지만, 스텍에 제일 마지막으로 들어간 데이터가 pop을 통해 제일 먼저 나오게 됩니다. 하지만 쌍이 맞지 않거나, 스택에 아무것도 데이터가 저장된 상태가 아님에도 불구하고 닫힌 괄호를 만난 상황이라면 false를 반환해야 합니다. 그리고 for loop을 다 돌았는데도, 스택이 비어있는 상태가 아니라면, 일부 열린 괄호가 스택에 저장된 상태로 for loop이 끝났다는 의미이기 때문에, 이 역시 false가 반환되어야 합니다. 이 모든 조건을 통과했을 때 비로소 true를 반환하게 되죠.

 

 

Valid Parentheses 문제의 솔루션 코드 중 제일 많은 추천을 받은 코드

 

그러면 다른 사람이 작성한 코드도 살펴보겠습니다. 이 코드도 역시 스택을 사용했는데요, 코드가 정말 간결하죠? 

 

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;  //taking stack for keep tracking the order of the brackets..
        for(auto i:s)  //iterate over each and every elements
        {
            if(i=='(' or i=='{' or i=='[') st.push(i);  //if current element of the string will be opening bracket then we will just simply push it into the stack
            else  //if control comes to else part, it means that current element is a closing bracket, so check two conditions  current element matches with top of the stack and the stack must not be empty...
            {
                if(st.empty() or (st.top()=='(' and i!=')') or (st.top()=='{' and i!='}') or (st.top()=='[' and i!=']')) return false;
                st.pop();  //if control reaches to that line, it means we have got the right pair of brackets, so just pop it.
            }
        }
        return st.empty();  //at last, it may possible that we left something into the stack unpair so return checking stack is empty or not..
    }
};

 

입력받은 string s에 대해서 for loop을 돌 때, 열린 괄호가 등장하면 스택에 저장합니다. 하지만 이후에 false가 발동하는 조건문에서 제 코드와 차이가 있네요. 이 분이 작성하신 코드에서는 for loop을 돌다가 닫힌 괄호를 만났을 때, 스택이 비어있거나, 현재 스택의 top에 위치한 열린 괄호 문자가 닫힌 괄호 문자랑 쌍을 이루지 못하는 경우는 전부 false로 처리하고 있습니다. 저와 반대의 케이스로 본거죠. 즉, 저는 현재 스택의 top에 위치한 열린 괄호 문자가 닫힌 괄호 문자랑 쌍을 이루는 3가지 경우를 각각 나눠서 처리를 했고, 이 분은 틀린 경우를 하나의 조건문 안에서 전부 처리를 하고 있습니다. 그리고 최종 결과로 스택이 비어있는지 아닌지의 여부를 반환하고 있습니다. 역시 저의 코테 실력은 갈 길이 멀군요.

 

 

<참고 자료>

 

1. 자료구조 스택에 대한 wikipedia 

 

 

 

지금까지 leetcode easy 난이도 문제 중 하나였던 valid parentheses 문제를 살펴보았습니다. 다음 문제도 이어서 포스팅 올리겠습니다.