Leetcode 2914. Minimum Number of Changes to Make Binary String Beautiful

문제

You are given a 0-indexed binary string s having an even length.

A string is beautiful if it's possible to partition it into one or more substrings such that:

Each substring has an even length.
Each substring contains only 1's or only 0's.
You can change any character in s to 0 or 1.

Return the minimum number of changes required to make the string s beautiful.

• 주어진 2의 배수 길이의 문자열이 있다.
• 이 문자열이 여러 2의 배수 길이의 0 혹은 1로만 이루어진 서브 문자열로 구성되게 하려면
• 얼마나 많은 문자열을 바꾸어야 하는가?

예시

1001

• 중간의 두 0을 둘다 1로 바꾼다
  • 1111, 즉 4개 길이의 1이 완성
• 혹은 양 끝의 1을 0으로 바꾸어도 된다.

제한

• $2 <= s.length <= 10^5$
• s는 2의 배수의 길이를 가진다.
• s는 0 혹은 1로만 이루어진다.

풀이

1. 점진적으로 분리하기

• 점진적으로 분리해가며 갯수를 찾아나간다.

class Solution:
    def minChanges(self, s: str) -> int:
        prefix_sum = [0] * len(s)

        prefix_sum[0] = 1 if s[0] == '1' else 0

        for i in range(1, len(s)):
            prefix_sum[i] = prefix_sum[i-1] + (1 if s[i] == '1' else 0)

        def range_sum(start: int, end: int):
            if start == 0:
                return prefix_sum[end]

            return prefix_sum[end] - prefix_sum[start - 1]

        cache = {}

        def count(start: int, end: int) -> int:

            if (start, end) in cache:
                return cache[(start, end)]

            size = end - start + 1

            partial = range_sum(start, end)
            if partial == 0 or partial == size:
                return 0

            change = min(partial, size - partial)

            if (size // 2) % 2 == 1:
                mid = (start + end) // 2 - 1
            else:
                mid = (start + end) // 2

            if size != 2:
                ans = min(change, count(start, mid) + count(mid + 1, end))
            else:
                ans = change

            cache[(start, end)] = ans
            return ans

        return count(0, len(s) - 1)

2. 그냥 2개씩 검사하면서 다르면 정답에 1 늘리기

class Solution:
    def minChanges(self, s: str) -> int:
        start = 0
        end = 1

        ans = 0

        while end < len(s):
            if s[start] != s[end]:
                ans += 1

            start += 2
            end += 2

        return ans

• 전형적인 Overthinking 함정 문제 ㅠ