ch9-1(leetcode 20). 유효한 괄호

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 20번 ( https://leetcode.com/problems/valid-parentheses/description/ )

 

풀이방법 1. 

스택을 이용해서 풀이한다. 

 

파이썬에는 별도의 스택이나 큐 자료구조가 없다. 리스트 자료형으로도 스택의 push()와 pop(), 큐의 enqueue(), dequeue() 메소드를 사용할 수 있다. 

다만 리스트는 포인터가 1개라서 리스트의 맨 앞에서 원소를 제거하는 데는 O(n)이 걸리므로, 성능을 생각한다면 collections 라이브러리의 deque 자료형을 쓰는 것이 더 빠르다. 

 

괄호는 여는 문자 (, [, { 와 닫는 문자 ), ], } 로 이루어져 있다. 

여는 문자가 나오면 스택에 넣는다. 닫는 문자가 나오면 스택의 맨 위의 여는 문자와 비교한 뒤, 일치하는 쌍이면 맨 위에서부터 괄호를 제거하고, 일치하지 않으면 False를 리턴하면 된다. 

또는 문자열이 아직 남아 있는데 스택이 빌 경우도 False를 리턴한다. 

마지막에 모든 문자열에 대해서 비교작업을 한 뒤, 스택이 비어 있는 경우에만 True를 리턴한다. 

 

스택은 저번처럼 좌우가 똑같은 문자열(팰린드롬)을 비교하는 등의 좌우대칭 문제뿐만 아니라, 괄호 등의 쌍을 비교하는 문제에서도 사용된다. 비슷한 유형이 나온다면 스택을 고려해 보자.