Python에서 괄호를 유효하게 만들기 위한 최소 추가

'(' 및 ')' 괄호의 문자열 S가 있다고 가정하고 결과 괄호 문자열이 유효하도록 임의의 위치에 최소 수의 괄호를 추가합니다. 괄호 문자열은 −

• 빈 문자열입니다.
• XY(X는 Y와 연결됨)로 작성할 수 있습니다. 여기서 X와 Y는 유효한 문자열입니다.
• (A)로 쓸 수 있습니다. 여기서 A는 유효한 문자열입니다.

따라서 문자열이 "()))(("과 같으면 문자열을 유효하게 만들기 위해 4개의 괄호를 더 추가해야 합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• S가 비어 있으면 0을 반환합니다.
• count :=0, temp는 배열, temp_counter :=0
• for i in S
  • 괄호를 여는 경우 temp에 i를 삽입합니다.
  • 그렇지 않으면
    • temp의 길이가 0이고 의 마지막 요소가 여는 괄호일 때 temp의 마지막 요소를 삭제하고, 그렇지 않으면 i를 temp에 삽입
• 온도의 크기를 반환합니다.

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution:
   def minAddToMakeValid(self, S):
      if not S:
         return 0
      count = 0
      temp = []
      temp_counter = 0
      for i in S:
         if i =='(':
            temp.append(i)
         else:
            if len(temp)>0 and temp[len(temp)-1] =='(':
               temp.pop(len(temp)-1)
            else:
               temp.append(i)
      return len(temp)
ob = Solution()
print(ob.minAddToMakeValid("()))(("))

입력

"()))(("

출력

4