[Python] Coda Kata Day8

문제

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

종류는 '(', ')', '[', ']', '{', '}' 으로 총 6개 있습니다.
아래의 경우 유효합니다.
한 번 괄호를 시작했으면, 같은 괄호로 끝내야 한다.
괄호 순서가 맞아야 한다.

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

s = "()"
return true

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

s = "(]"
return false

s = "([)]"
return false

s = "{[]}"
return true

내코드

def is_valid(string):
  # 열림이 나오고 닫힘이 나올때 해당 닫힘이 아니면 오류
  # open이냐 close냐, 누구의 짝이냐
    braces = {'(':['open', ')'], '[':['open', ']'], '{':['open', '}'], ')':['close', '('],  ']':['close', '['],  '}':['close', '{']}
  
  if len(string) <=1:
    return False
    
  if braces[string[0]][0]=='close':
    return False
    
  for i in range(len(string)-1):
    current_brace = string[i]
    next_brace = string[i+1]
    print(f'current_brace: {current_brace}, next_brace: {next_brace}')
    print(f'braces[current_brace][0]:{braces[current_brace][0]}, braces[next_brace][0]: {braces[next_brace][0]}')
    
    if braces[current_brace][0]=='open' and braces[next_brace][0]=='close':
      if braces[next_brace][1] == current_brace:
        print(f'if braces[next_brace][1]({braces[next_brace][1]}) == current_brace({current_brace}:')
        return True
      else:
        return False
   return "end"

사실 하다가 경우의 수가 많아져서(내 코드가 망하고 있다는 징조...) 나중에는 그냥 test 예시에 끼워 맞췄다...🤯🤯🤯 결론은 실패~

Model Solution

def is_valid(string):
	left = ['(', '{', '[']
	right = [')', '}', ']']
	stack = []
	for letter in string:
		if letter in left:
			stack.append(letter)
		elif letter in right:
			if len(stack) <= 0:
				return False
			if left.index(stack.pop()) != right.index(letter):
				return False
	return len(stack) == 0

이 문제에서 false가 생기는 경우는 크게 2가지이다.
1. 순서대로 괄호가 안닫혔을때
2. 괄호 짝(lett, right)이 맞지 않을때

만약 괄호가 이렇게 여러개 열렸다면 ([{, 마지막에 열린 괄호부터 차례차례 닫혀야한다.
일단 left에 해당하는 괄호(열린 괄호)가 나오면 stack에 append해준다. 그리고 right 괄호가 등장한다면 이 괄호는 가장 마지막에 등장한 괄호를 닫아주어야 하기 때문에 pop을 사용하여 가장 마지막으로 등장한 left괄호의 짝인지 확인한다(서로의 리스트의 index가 동일해야함).

하지만 여기서도 예외가 발생할 수 있다. 만약 stack에 담긴 left괄호가 없는데 비교할 right괄호만 있다면 오류상황 2번에 해당하는 경우이므로 False를 return해준다.

그리고 주어진 string을 다 돌았는데 stack에 요소가 남아있다면 해당 left에 해당하는 right가 등장하지 않은 것이므로 오류상황 2번에 해당하므로 len(stack)이 0이 아니면 False를 return하고 0이면 True를 return한다.

• index 함수: index(x) 함수는 리스트에 x 값이 있으면 x의 위치 값을 돌려준다.
• pop 함수: pop()은 리스트의 맨 마지막 요소를 돌려주고 그 요소는 삭제한다.