[LeetCode][Kotlin] 1963. Minimum Number of Swaps to Make the String Balanced

1963. Minimum Number of Swaps to Make the String Balanced

You are given a 0-indexed string s of even length n. The string consists of exactly n / 2 opening brackets '[' and n / 2 closing brackets ']'.

A string is called balanced if and only if:

• It is the empty string, or
• It can be written as AB, where both A and B are balanced strings, or
• It can be written as [C], where C is a balanced string.

You may swap the brackets at any two indices any number of times.

Return the minimum number of swaps to make s balanced.

짝수 길이 n의 0 인덱스 문자열 s가 제공됩니다. 문자열은 정확히 n/2개의 여는 괄호 '['와 n/2개의 닫는 괄호 ']'로 구성됩니다. 

다음과 같은 경우에만 문자열을 균형이라고 합니다. 
- 빈 문자열이거나 
- A와 B가 모두 균형을 이루는 문자열인 AB로 작성할 수 있습니다. 
- [C]로 쓸 수 있습니다. 여기서 C는 균형 잡힌 문자열입니다. 

두 인덱스의 대괄호는 여러 번 바꿀 수 있습니다. 

s를 균형있게 만들기 위한 최소 스왑 수를 반환합니다.

 

Example 1:

Input: s = "][]["

Output: 1

Explanation: You can make the string balanced by swapping index 0 with index 3.

The resulting string is "[[]]".

 

Example 2:

Input: s = "]]][[["

Output: 2

Explanation: You can do the following to make the string balanced:

- Swap index 0 with index 4. s = "[]][][".

- Swap index 1 with index 5. s = "[[][]]".

The resulting string is "[[][]]".

 

Example 3:

Input: s = "[]"

Output: 0

Explanation: The string is already balanced.

 

Constraints:

• n == s.length
• 2 <= n <= 10^6
• n is even.
• s[i] is either '[' or ']'.
• The number of opening brackets '[' equals n / 2, and the number of closing brackets ']' equals n / 2.

---

코드

• 최소 스왑 수는 이미 균형을 이루는 괄호를 제외한 불균형을 이루는 괄호의 수에서 1을 더하고, 2를 나눈 값과 같다.

class Solution {
    fun minSwaps(s: String): Int {
        var closed = 0
        for (c in s) {
            if (c == '[') closed++
            else if (closed > 0) closed--
        }
        return (closed + 1) / 2
    }
}