Score of Parentheses [leetcode]

문제

 

문제풀이 설명

하...또 쉬워보여서 도전했다가 오지게 오래걸려서 풀었다. (그래도 풀었다는게 대견쓰)

규칙에 따라서 괄호를 숫자로 변경한 뒤, 모든 숫자의 합을 구하는 문제다. (규칙은 위에 써져 있다.)

 

분명 말하지만 이미 밸런스한 상태라 스택이 필요없다.

괄호를 어떻게 치환하는지가 관건이다. 처음에는 “()”를 “|” 로 치환했었다.

그렇게 변경할 경우 | 양옆에 괄호를 보고 값을 구할 수 있을거라 생각했었지만, (()()) 의 경우에는

( | | ) 로 변하고, (()(()())) 인 경우에는 ( | ( | | ) ) 등 로직을 구성하는데 있어서 언제 더하고, 언제 기다릴지 에

대한 로직이 뚜렷하게 보이지 않았다.

 

몇번의 불통 끝에 하나 발견한 사실은 처음 등장하는 “)(” 을 기준으로 양옆으로 나눈뒤, ()의 개수를 맞춰주면

나눠진 문자열 기준으로 앞 문자열은 “(”의 개수와 “)”의 개수가 동일한 밸런스 문자열이 되는걸 알아냈다.

1. (()()) → (() )( ()) → (()) , (())
2. ()(())→ ( )( ()) → () , (())
3. ((()())()) → ((( )( ))()) → ((())), ((())())

그렇다면 저 첫번째 값은 무조건 2의 (“(” 갯수 -1) 승이 된다. (= 2^{ count(”(”)-1 } )

그럼 문자열을 반복적으로 “)(” 으로 나누면서 앞의 값은 위 2의 n승 대로 더해주면 끝!

 

class Solution:
    def deeper(self, s):
        # print(s)
        answer = 0
        if ")(" in s:
            temp_list = s.split(")(",1)
            for i in range(len(temp_list)):
                bra = temp_list[i]
                left = bra.count("(")
                right = bra.count(")")
                if left > right:
                    for k in range(left-right):
                        temp_list[i] += ")"
                else:
                    for k in range(right-left):
                        temp_list[i] = "("+temp_list[i]
            
            answer = 0
            for bra in temp_list:
                answer += self.deeper(bra)
        else:
            answer = 1
            answer *= (2**(s.count("(")-1))
            
        return answer   
    def scoreOfParentheses(self, s: str) -> int:
        answer = self.deeper(s)
        return answer

 

결과는~