We.TIL 번외 : Stack 관련 코드카타

What is Stack?

스택은 가장 나중에 들어온 자료가 가장 먼저 처리되는 LIFO(Last-In-First-Out)자료구조이다.
구멍이 하나밖에 없는 병이라고 생각하면 이해하기 쉽다.

파이썬에서 스택구현

stack = []

파이썬에서는 리스트로 스택을 흉내낸다. 따라서 스택 자료구조를 초기화 할 때는 빈 리스트를 생성해준다.

stack push

스택에 원소를 넣을 때는 append 메소드를 통해 리스트 가장 마지막에 원소를 넣도록 한다.

stack -pop

스택에서 원소를 제거할 때는 pop메소드를 이용해 리스트의 가장 마지막 원소를 제거해준다.
이때, pop 메소드에 의해 제거한 원소를 리턴받을 수 있다.

stack -top

스택에서 원소를 제거하지 않고 가져오기만 할 때에는 [-1]을 이용한다.

문제

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

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

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

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

s = "()"
return True

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

s = "(]"
return False

s = "([)]"
return False

s = "{[]}"
return True

해결

def is_valid(s):
  stack = []  
  # 스택선언 
  
  mapping = {')':'(','}':'{',']':'['}
  # Key값으로 닫는표시가 표시되어있는 mapping dictionary 생성
  (저런 closing bracket을 뚜껑, 반대모양인 opening bracket을 그릇이라고 명명하자)
  
  for i in s :
  # i가 s의 인자이고
  
    if i in mapping :
    # i가 만약 ) or } or ] 이라면(뚜껑들)
    
      top_element = stack.pop() if stack else None
      # 스택이 비어있지 않다면 top_element 맨 마지막 요소를 뜯어낸다 
      (이 경우 else로 받은 그릇들만 오게됨)
      
      if mapping[i] != top_element:
        return False
      # mapping 딕셔너리는 key와 value를 같은 종류의 그릇+뚜껑으로 구성. 그러므로 뜯어낸 그릇(value)과 들어온 key(뚜껑)에 맞는 value가 동일하지않다면 동일한 종류의 뚜껑+그릇이 아니다.(성립될수없다).. False 반환
      
    else :
      stack.append(i)
     # i가 만약에 ( or { or [ (그릇들) 이라면 스택안에 넣는다.
  
  return not stack
  # 이 의미는 return not False if stack == []와 같다.
  # 만약에 스택이 [](빈리스트)라면 0=false 'not false'는 'True'이므로 True를 반환
  # 만약에 스택이 [{](들어있는리스트라면) 0<이므로 True 'not True'는 'False'이므로 False반환

LeetCode의 표준답변으로 코드가 간략하게 작성되어있어 한번에 이해가 어려울 수 있다.
특히 not stack이 len(stack) == 0 이면 True를 반환시킨다는 함축된 코드식을 처음 깨달았다.