Leetcode #20 Valid Parentheses

문제

s는 여러 괄호들로 이루어진 String 인자입니다.
s가 유효한 표현인지 아닌지 true/false로 반환해주세요.

종류는 '(', ')', '[', ']', '{', '}' 으로 총 6개 있습니다. 아래의 경우 유효합니다.

한 번 괄호를 시작했으면, 같은 괄호로 끝내야 한다.
괄호 순서가 맞아야 한다.

예를 들어 아래와 같습니다.

s = "()"
return true

s = "()[]{}"
return true

s = "(]"
return false

s = "([)]"
return false

s = "{[]}"
return true

나의 풀이

처음 접근은 Stack 자료구조를 모른 상태에서 시작했다.
딕셔너리를 만들고 각 괄호가 짝이 있다는 점을 이용해 인덱스의 합이 len(dict)인 점을 이용하려고 했다.
그러다가 괄호 안에 또다른 괄호가 나오는 경우를 대처하지 못했고 결국 다른 방법을 시도하게 되었다.
그래서 검색하다가 알게 된 것이 Stack이다.

스택이란?

스택은 Last-In-First-Out(LIFO)의 특성을 가지는 자료구조를 일컫는다. 스택은 자료의 입력과 출력이 한쪽 끝에서만 가능하다. 스택에서 자료를 넣는 것을 push라고 하고, 꺼내는 것을 pop이라고 한다. 자료가 꺼내질 때는, 가장 최근에 push한 자료가 나오게 된다.

이것을 문제에 적용하면, 다음 조건을 만족해야 한다.

• 주어진 string을 순회하는 for문과, 스택 자료구조 역할을 할 빈 리스트를 선언한다.
• 괄호의 시작 부분이 나오면 push한다.
• 닫는 부분이 나오면 시작 부분이 있다는 가정 하에 똑같은 짝을 pop한다.
• 똑같은 짝이 없다면 False를 반환한다.
• 조건을 만족한다면 스택은 비어있을 것이다. 빈 스택이면 True를 반환하고 그렇지 않으면 False를 반환한다.

해당 로직을 코드로 구현해 보았다.

def is_valid(string):
  list1 = ['(','{','[']					 # 괄호 리스트 선언 
  list2 = [')','}',']']
  result = []						 # Stack 역할을 할 빈 리스트 선언
  for i in string:
    if i in list1:					 # 괄호의 여는 부분이면 
      result.append(i)					 # 스택의 push에 해당하는 append()
    elif i in list2 and list1[list2.index(i)] in result: # 괄호의 닫는 부분이고 짝이 Stack에 존재한다면
      result.pop()					 # 스택의 pop에 해당하는 pop()
    else: 						 # 짝이 없다면 False 반환
      return False

  return len(result)==0					# 빈 스택이면 True 반환, 아니면 False 반환