[LeetCode] 20. Valid Parentheses

https://leetcode.com/problems/valid-parentheses/description/?envType=study-plan-v2&envId=top-interview-150 

Valid Parentheses - LeetCode

문제 유형 : 스택

문제 난이도 : Easy

 

문제

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.

 

열린 괄호는 같은 종류의 괄호로 닫혀야 하고, 닫는 순서를 지켜야 한다(늦게열린게 먼저 닫혀야한다.)

문자열 s가 규칙을 지키는지 확인하는 코드를 작성하시오

 

 

풀이

스택을 생성한 뒤, 문자열 s를 인덱스 0부터 탐색한다. 여는 괄호인 경우에는 스택에 추가한다.

스택이 비어있는지 확인한다. 비어있으면 첫 글자부터 여는 괄호로 시작하지 않는다는 뜻이므로 false를 반환해주면 된다.

닫는 괄호인 경우에는, 스택의 최상단에 있는 문자(여는괄호)와 같은 종류인지 확인한다.

같은 종류가 아니라면, 바로 false를 반환해준다.

 

문자열 s를 모두 순회하고 나서도 스택이 비어있지 않다면, false를, 아니면 true를 반환해주면 된다.

 

 

코드(C++)

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

        return stk.empty();
    }
};