Python을 사용하여 괄호 문자열의 균형을 맞추기 위해 최소 삽입을 찾는 프로그램

여는 괄호와 닫는 괄호 '(' 및 ')'가 있는 문자열 s가 있다고 가정합니다. -

• 왼쪽 괄호 '('에는 해당하는 두 개의 연속 오른쪽 괄호 '))'가 있습니다.

• 왼쪽 괄호 '('는 해당하는 두 개의 연속되는 오른쪽 괄호 ')))'보다 먼저 와야 합니다.

예를 들어 "())", "())(())))"는 균형이 맞지만 ")()", "()))"는 균형이 맞지 않습니다. 이러한 문자열이 있는 경우 문자열의 균형을 맞추기 위해 괄호(열기 또는 닫기)의 수를 계산해야 합니다.

따라서 입력이 s ="(())))))"와 같으면 출력은 1이 됩니다. 왜냐하면 그것을 분할하면 "( ()) )) ))"를 얻을 수 있기 때문입니다. 하나의 왼쪽 괄호를 사용하여 "( ()) ()) ))" 문자열을 만들어 균형을 맞춥니다.

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

• :=0, n :=s의 크기

• ret :=0, 나는 :=0

• 내가

  • s[i]가 '('와 같으면

• :=o + 1

  • 그렇지 않으면

    • i + 1

      • o가 0이면

        • 렛 :=렛 + 1

      • 그렇지 않으면

• :=o - 1

  • 나는 :=나는 + 1

  • 그렇지 않으면

    • 렛 :=렛 + 1

    • o가 0이면

      • 렛 :=렛 + 1

    • 그렇지 않으면

• :=o - 1

  • 나는 :=나는 + 1

• 리턴 ret + 2 * o

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

예시

def solve(s):
   o = 0
   n = len(s)
   ret = 0
   i = 0
   while i < n:
      if s[i] == '(':
         o += 1
      else:
         if i + 1 < n and s[i + 1] == ')':
            if not o:
               ret += 1
            else:
               o -= 1
               i += 1
         else:
            ret += 1
            if not o:
               ret += 1
            else:
               o -= 1
      i += 1
   return ret + 2 * o
s = "(())))))"
print(solve(s))

입력

"(())))))"

출력

3