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

문제 1. 괄호로 입력된 값이 올바른지 판별하라.

EX1_입력 ] ()[]{}
EX1_출력 ] true

 

해당 문제를 푸는 방법?!

- 스택 일치 여부 판별 ( 딕셔너리 테이블 사용 )

 

1. 스택 일치 여부 판별

def isValid( s) :
    table ={
        ')':'(',
        ']': '[',
        '}': '{',
    }
    stack = []
    
    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 #알맞은 입력일 경우 스택이 비어서 종료
    
print(isValid("()[]{}"))

- 딕셔너리에서 in 또는 not in은 키 값에서 검색한다.  즉 키 in 딕셔너리 형태가 되는 것

  ( in의 경우 특정 키가 있으면 true, 없으면 false )

 

- 여는 괄호를 스택에 집어 넣고 닫는 괄호는 나올때 stack에서 마지막 것을 pop 한 것의 table의 value값과 다르면 여는 괄호와 닫는 괄호가 불일치 이므로 false 리턴

 

- 리스트를 사용하여 품. 파이썬 리스트의 경우 스택 연산인 푸시와 팝이 O(1)의 성능을 가짐. 

 

---

[ 참고자료 ]

- 도서 : 파이썬 알고리즘 인터뷰 

파이썬 알고리즘 인터뷰 - 교보문고