Python 알고리즘 인터뷰 - 문제20. 유효한 괄호

leetcode 20. Valid Parentheses

https://leetcode.com/problems/valid-parentheses/description/

 

문제

괄호로 된 입력된이 올바른지 판별하라

예제

입력

()[]{}

 

출력

True

 

풀이

문제의 입력값이 괄호만 존재하는지, 아니면 다른 문자가 같이 섞여있는지에 따라 코드가 달라진다. 처음 풀이할 때 다음과 같이 문자가 있는 경우를 가정하고 풀었기 때문에 해당 코드로 진행하였다.

 

<입력값에 대한 처리 리스트>

"(a{b[cd]e}f)" -> True

")", "(" -> False

"[abc}" -> False

 

우선 문자열에서 현재 위치 문자를 ch라고 했을 때 ,여는 괄호( '(', '{', '[' )를 만나면 stack에 push, 일반 문자면 pass하면서 진행한다.

이후 닫는 괄호( ')', '}', ']' ) 를 만나면 스택에서 최상단의 여는 괄호와 같은지 비교한다. 같은 pair이면 pass하고 아니면 실패이므로 return False 한다.

루프를 모두 마쳤을 때 stack에 값이 남아있다는 것은 여는 괄호는 있는데 닫는 괄호가 없다는 뜻이므로 실패 처리한다.

전체 코드는 다음과 같다.

def isValid(s):
    closes = [')', ']', '}']
    pairs = {'(': ')', '[': ']', '{': '}'}
    st = []
    for ch in s:
        if ch in pairs:
            st.append(ch)
        if ch in closes:
            if len(st) == 0:
                return False

            if pairs[st.pop()] != ch:
            	return False

    return len(st) <= 0