leetcode 20. Valid Parentheses 유효한 괄호 문제 풀이

<파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 풀이한 포스팅이다.

 

문제는 모두 리트코드에 출제된 문제들이며, 직접 풀었지만, 책에서 주는 힌트와 풀이 과정들을 참고한 경우가 많다.

이곳은  정리한 책에 나온 문제에 대한 목록과 해설을 정리한 공식 깃허브 페이지 이며, 

다음 포스팅은 내가 푼 <파이썬 알고리즘 인터뷰> 문제 풀이 목록을 정리해 놓았다.

 

문제

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

 

입력: 괄호로 구성된 문자열

출력: boolean

 

문제 요약: 괄호는 항상 마지막에 오는 여는 괄호의 닫힌 괄호가 먼저 나와야 한다. 즉, (){} 이나 ({}) 는 True이지만, {(}) 는 마지막 여는 괄호 ( 에 맞는 )가 오지 않았으므로 False 이다.

그리고 모든 괄호들이 닫혀야지만, True이고 {() 처럼 닫는 괄호가 없는 경우에는 False이다.

 

유의 사항: 난이도를 쉽게 하기 위해서인지 괄호 이외의 다른 아이템은 없고 비어있는 string이 입력으로 오지도 않는, 비교적 예외사항이 적은 문제이다.

생각 과정

가장 마지막에 열린 괄호에 맞는 닫힌 괄호가 나와야 하므로, LIFO인 스택 자료 구조를 활용하는 것이 찰떡인 문제이다.

파이썬에서 스택은 그냥 리스트 자료형을 쓰면 된다.

열린 괄호는 리스트에 넣고,

.pop()으로 나오는 마지막 열린 괄호와 새로 들어오는 닫힌 괄호가 맞으면, 그것들은 빼고,

그 다음 마지막에 있는 열린 괄호와 새로 들어오는 닫힌 괄호가 맞으면 또 빼고...

이렇게 마지막까지 한 다음에 리스트에 남은 괄호가 없으면 완결된 구조,

남는 게 있으면 괄호가 다 처리되지 않았으므로 False를 return 하면 된다.

 

그리고 열린 괄호와 닫힌 괄호의 짝이 맞아야 하는데, 이를 편리하게 위해 key-value가 있는 hash 자료 구조롤 활용한다.

그리고 key로만 탐색이 되기 때문에 닫는 괄호를 key로 넣어서 활용하는게 더 편하다.

 

 

 

풀이

def solution(s):
    stack = []
    dic = {')': '(',
       ']': '[',
       '}': '{'}
    for i in s:
        print(i)
    #여는 괄호 들어오면 무조건 저장
        if i not in dic:
            stack.append(i)
            print('stack',stack)
        #닫는 괄호면 stack.pop()과 같으면 통과
        elif not stack or stack.pop() != dic[i]:
            return False
    #s의 마지막 아이템까지 탐색했을 때, 남는 괄호가 하나도 없으면 True 아니면 False
    return len(stack) == 0