leetcode 1963. Minimum Number of Swaps to Make the String Balanced

문제 링크 : https://leetcode.com/problems/minimum-number-of-swaps-to-make-the-string-balanced/

Minimum Number of Swaps to Make the String Balanced - LeetCode

문제에서는 balanced라는 표현을 쓰고 있지만 balanced의 조건을 잘 생각해보면 결국 valid parentheses여야 balanced라는 것을 알 수 있다. 즉, 여는 괄호와 닫는 괄호의 짝이 맞아야 한다는 것 이다.

 

그러므로 짝이 안맞는 괄호의 수를 세어주고 그들의 위치를 swap해주면 balanced하게 된다.

이렇게 swap한 횟수가 답이므로 짝이 안맞는 괄호의 수를 세어주기만 하면 바로 답을 알 수 있다.

 

class Solution:
    def minSwaps(self, s: str) -> int:
        balance = 0
        min_bal = 0
        for c in s:
            if c == '[':
                balance += 1
            else:
                balance -= 1
            min_bal = min(min_bal, balance)
        return (-min_bal + 1)//2

위의 코드에서 balance의 최소값이 음수가 되면 짝이 안맞는 괄호가 존재한다는 의미이다.