[파이썬 알고리즘 인터뷰][스택/큐] 유효한 괄호

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

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

 

책에서 구현된 코드

def isValid(self, s: str) -> bool:
    stack = []
    table = {
        ')': '(',
        ']': '[',
        '}':'{'
    }
    
    for char in s:
        if char not in table:
            stack.append(char)
        elif not stack or table[char] != stack.pop():
            return False
    
    return len(stack) == 0

 

기억해야할 기법

• for의 in에 dict는 key로 비교한다
• bool로 return할 시, 비교 연산 사용이 깔끔한듯

 

내가 구현한 코드

def isValid(s: str) -> bool:
    #(){}[]
    pair = {')':'(', ']':'[', '}':'{'}
    push_list = pair.values()
    stack = []
    for c in s:
        if c in push_list:
            stack.append(c)
        else:
            if not stack or stack.pop() != pair[c]:
                return False

    return True if not stack else False


if __name__ == '__main__':
    print(isValid(
        "(]"
    ))

• 내가 구현한 알고리즘

• 책에서 구현한 알고리즘

• 차이가 커보여서 놀랐다
• 어느 근소한 차이에서 이렇게 차이를 보이나 찾아봤지만, 내가 구현한 알고리즘도 몇 번 돌리니 비슷한 속도로 측정됐다