[2021][01]Valid Parenthesis

문제정보

문제요약

주어진 문자열 s가 주어졌을 때 올바른 문자열인지 아닌지를 판단하라. 올바른 문자열은 다음 규칙으로 판단한다.
1. 열린 괄호는 반드시 같은 종류의 괄호로 닫혀야 한다. (예시: ())
2. 열린 괄호는 반드시 정확한 순서로 닫혀야 한다. (예시: [(]) -> False)

제약사항

• 1 <= s.length <= 10000
• s는 다음 리스트 안의 괄호로만 구성 '(', ')', '{', '}', '[', ']'

접근방법

스택을 이용하여 문제를 풀었다.
1. 각 괄호 종류의 갯수를 세서 열린 괄호와 닫힌 괄호의 갯수가 동일한지 판단한다. 동일하지 않다면 2번 과정으로 진행할 필요 없이 False 를 반환한다.
2. 문자열 s를 처음부터 끝까지 순회하면서 열린 괄호가 들어오면 스택에 집어넣는다.
3. 스택이 빈 상태인데 닫힌 괄호를 순회 중이라면 잘못된 문자열이므로 False를 반환한다.
4. 스택에 저장된 마지막 괄호와 순회 중인 문자열의 괄호가 쌍을 이루면(같은 종류의 괄호이면) 스택에서 저장된 마지막 괄호를 꺼낸다.
5. 문자열 s 순회를 마쳤다면 올바른 문자열이므로 True를 반환한다.

코드

class Solution:
    def isValid(self, s: str) -> bool:
        stc = []
        counter = Counter(s)
        if counter['('] != counter[')'] or counter['['] != counter[']'] or counter['{'] != counter['}']:
            return False
        i = 0
        n = len(s)
        left = ['{', '[', '(']
        right = ['}', ']', ')']
        while i < n:
            if s[i] in left:
                stc.append(s[i])
                i += 1
                continue
            if not stc and s[i] in right:
                return False
            if right.index(s[i]) == left.index(stc[-1]):
                stc.pop()
                i += 1
                continue
            else:
                return False
        return True