문제

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

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

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

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

s = "()"
return true

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

s = "(]"
return false

s = "([)]"
return false

s = "{[]}"
return true

풀이

나는 결국 풀지 못했기 때문에, 나의 풀이는 없다,,

#1

어찌 됐든 서로 만나는 짝꿍 괄호가 있기 때문에, 만나는 것들을 하나씩 삭제해 나가고
마지막에 string이 비었을 때 True를 반환하는 방법

def is_valid(string):
    A = '()'
    B = '{}'
    C = '[]'

    if len(string) % 2 == 1:
      return False

    for i in range(len(string) // 2):    # 짝으로 찾을거니까 range는 string 길이의 반
      if A in string:
        string = string.replace(A, '')
      elif B in string:
        string = string.replace(B, '')
      elif C in string:
        string = string.replace(C, '')
    
    if string == '':
      return True
    else:
      return False

#2

열리는 괄호들을 만나면 stack 리스트에 쌓아주고,
가장 마지막에 쌓인 열린 괄호와 짝꿍인 닫는 괄호를 만나면, stack에서 해당 열린 괄호를 삭제하는 방법

def is_valid(string):
  p_dict = {')': '(', ']': '[', '}': '{'} 

  stack = []

  for i in string:
    if i in p_dict.values():
      stack.append(i)
    else:
      # list.pop() 반환값은 제일 마지막 값
      # 반환 후 list에서 마지막 값이 사라짐
      if not stack or p_dict[i] != stack.pop():    # pop의 반환값과 비교
        return False
   
  return not stack

자료구조: Stack

• 한쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료구조
  
  ex) 웹 브라우저에서 뒤로가기 버튼
  
  현재 내가 보고 있는 페이지가 가장 위에 있는 페이지이고, 가장 위에 있는 페이지를 제거하면(뒤로가기) 그 바로 앞에 있던 페이지로 돌아감