올바른 괄호

• ❓ Q.
  괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻이다. 예를 들어

  ()() 또는 (())() 는 올바르다.
  )()( 또는 (()( 는 올바르지 않다.

  이 때, '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 True 를 반환하고 아니라면 False 를 반환하시오.

  "(())()" # True
  "(((("   # False

  def is_correct_parenthesis(string):
     # 구현해보세요!
     return
  
  
  print("정답 = True / 현재 풀이 값 = ", is_correct_parenthesis("(())"))
  print("정답 = False / 현재 풀이 값 = ", is_correct_parenthesis(")"))
  print("정답 = False / 현재 풀이 값 = ", is_correct_parenthesis("((())))"))
  print("정답 = False / 현재 풀이 값 = ", is_correct_parenthesis("())()"))
  print("정답 = False / 현재 풀이 값 = ", is_correct_parenthesis("((())"))

• 💡 내 코드

  def is_correct_parenthesis(string):
     stack = []
     print(range(len(string)))
  
     for i in range(len(string)):
         if string[i] == "(":
             stack.append(i)     # stack = [ (, ( ]
         elif string[i] == ")":
             if len(stack) == 0:
                 return False
             stack.pop()         # stack = [ ]
  
     if len(stack) != 0:         # len(stack) == 0
         return False
     else:
         return True             # True 반환
  
  
   print("정답 = True / 현재 풀이 값 = ", is_correct_parenthesis("(())"))

  
  

• 🚩 해결방법
  괄호가 잘 닫혔는지 아닌지 여부를 어떻게 하면 알 수 있을까요?

  생각이 안 나시면, 혼자 그냥 문자열을 순차탐색 해보시는 것도 좋은 방법입니다.

  "(())" 을 예시로 들어보겠습니다!

  1. ( → 괄호가 하나 열렸습니다.

  2. ( → 괄호가 또 하나 열렸네요.

  3. ) → 괄호가 하나 닫혔습니다. 이 괄호는 뭐랑 닫힌 건가요?
     직전에 열린 2의 (랑 닫힌 거겠네요.

  4. ) → 괄호가 하나 닫혔습니다. 이 괄호는 뭐랑 닫힌 건가요?
     직전 직전에 열린 1의 (랑 닫힌 거겠네요.

     "((()" 을 예시로 들어보겠습니다!

  1. ( → 괄호가 하나 열렸습니다.
  2. ( → 괄호가 또 하나 열렸네요.
  3. ( → 괄호가 또 하나 열렸네요.
  4. ) → 괄호가 하나 닫혔습니다. 이 괄호는 뭐랑 닫힌 건가요? 
          직전에 열린 3의 (랑 닫힌 거겠네요.

어! 끝났는데 아직 열린 애들이 있네요. 이건 올바르지 않은 괄호네요!

이런 느낌으로 생각을 하다보면 두 가지 아이디어가 떠오르실거에요.

1) 닫는 괄호가 나오면 바로 직전에 열린 괄호가 있는지 봐야 한다.
2) 열린 괄호들을 다 저장해놔야겠다.

바로 직전 데이터를 쌓는 좋은 자료구조가 있었죠. 바로 스택입니다!

문자열을 돌면서 문자가 "(" 이라면 스택에 쌓아놓습니다.
그리고 ")" 가 나오면, 직전 스택에 저장되어 있는지 확인합니다.
만약 없다면? 닫는 것은 있는데 여는 게 없으니 False 를 반환합니다.
만약 있다면 가장 상위의 원소를 제거하면 되겠죠.

이 과정을 쭉 반복하다가, 문자열이 끝났는데 아직 stack 이 남아있다?
그러면 닫아주는 게 부족했으니 False 입니다! 만약 전부 없어졌다면 True 를 반환하시면 됩니다.