Leetcode 3501. Maximize Active Section with Trade II

You are given a binary string s of length n, where:

'1' represents an active section.
'0' represents an inactive section.
You can perform at most one trade to maximize the number of active sections in s. In a trade, you:

Convert a contiguous block of '1's that is surrounded by '0's to all '0's.
Afterward, convert a contiguous block of '0's that is surrounded by '1's to all '1's.
Additionally, you are given a 2D array queries, where queries[i] = [li, ri] represents a substring s[li...ri].

For each query, determine the maximum possible number of active sections in s after making the optimal trade on the substring s[li...ri].

Return an array answer, where answer[i] is the result for queries[i].

Note

For each query, treat s[li...ri] as if it is augmented with a '1' at both ends, forming t = '1' + s[li...ri] + '1'. The augmented '1's do not contribute to the final count.
The queries are independent of each other.

• 길이가 n인 이진 문자열 s가 주어진다.

  • '1'은 활성 구간을 나타낸다.
  • '0'은 비활성 구간을 나타낸다.

• 문자열 s에서 활성 구간의 개수를 최대화하기 위해 최대 한 번의 트레이드를 수행할 수 있다.

• 한 번의 트레이드는 다음 두 단계로 이루어진다.

  • 양쪽이 '0'으로 둘러싸인 연속된 '1' 블록 하나를 모두 '0'으로 바꾼다.
  • 그다음, 양쪽이 '1'로 둘러싸인 연속된 '0' 블록 하나를 모두 '1'로 바꾼다.

• 추가로 2차원 배열 queries가 주어진다.

  • queries[i] = [li, ri]는 부분 문자열 s[li...ri]를 나타낸다.

• 각 쿼리에 대해 다음 값을 구하라.

  • 부분 문자열 s[li...ri]에서 최적의 트레이드를 수행했을 때 얻을 수 있는 활성 구간의 최대 개수

• 각 쿼리의 결과를 담은 배열 answer를 반환하라.

  • answer[i]는 queries[i]에 대한 결과이다.

• 참고

  • 각 쿼리에서는 s[li...ri]의 양쪽에 '1'을 하나씩 추가한 것처럼 취급한다.
    • 확장된 문자열은 t = '1' + s[li...ri] + '1'이다.
  • 양쪽에 추가된 '1'은 최종 활성 구간 개수에 포함되지 않는다.
  • 각 쿼리는 서로 독립적으로 처리한다.

---

예시

(1)

• 입력

  • s = "01"
  • queries = [[0, 1]]

• 출력

  • [1]

• 설명

  • 양쪽이 '0'으로 둘러싸인 '1' 블록이 존재하지 않으므로 유효한 트레이드를 수행할 수 없다.
  • 따라서 활성 구간의 최대 개수는 1이다.

(2)

• 입력

  • s = "0100"
  • queries = [[0, 3], [0, 2], [1, 3], [2, 3]]

• 출력

  • [4, 3, 1, 1]

• 설명

  • 쿼리 [0, 3]

    • 부분 문자열: "0100"
    • 양쪽에 '1'을 추가하면: "101001"
    • "0100"을 선택한다.
    • "0100" → "0000" → "1111"로 변환한다.
    • 양쪽에 추가한 문자를 제외한 최종 문자열은 "1111"이다.
    • 활성 구간의 최대 개수는 4이다.

  • 쿼리 [0, 2]

    • 부분 문자열: "010"
    • 양쪽에 '1'을 추가하면: "10101"
    • "010"을 선택한다.
    • "010" → "000" → "111"로 변환한다.
    • 원래 문자열 전체에서의 최종 상태는 "1110"이다.
    • 활성 구간의 최대 개수는 3이다.

  • 쿼리 [1, 3]

    • 부분 문자열: "100"
    • 양쪽에 '1'을 추가하면: "11001"
    • 양쪽이 '0'으로 둘러싸인 '1' 블록이 존재하지 않으므로 유효한 트레이드를 수행할 수 없다.
    • 활성 구간의 최대 개수는 1이다.

  • 쿼리 [2, 3]

    • 부분 문자열: "00"
    • 양쪽에 '1'을 추가하면: "1001"
    • 양쪽이 '0'으로 둘러싸인 '1' 블록이 존재하지 않으므로 유효한 트레이드를 수행할 수 없다.
    • 활성 구간의 최대 개수는 1이다.

---

제한

• $1 <= n == s.length <= 10^5$
• $1 <= queries.length <= 10^5$
• s[i] 의 값은 '0' 혹은 '1' 이다.
• $queries[i] = [l_i, r_i]$
• $0 <= l_i <= r_i < n$

---

풀이

• 한 번의 트레이드에서는 두 0 블록 사이에 있는 1 블록을 먼저 0으로 바꾼 뒤, 하나로 합쳐진 전체 0 블록을 다시 1로 바꾼다.
• 이 과정에서 가운데 1 블록은 잠시 0이 되었다가 다시 1로 돌아오므로 최종 활성 구간 수의 증가량에는 영향을 주지 않는다.
• 따라서 실제 증가량은 선택한 1 블록의 왼쪽 0 길이 + 오른쪽 0 길이가 된다.
• 다만 이번 문제는 이전 문제와 달리 쿼리가 최대 10^5개이므로, 각 쿼리에서 가능한 모든 0 블록 쌍을 직접 확인할 수 없다.
• 문자열을 전처리한 뒤, 이진 탐색과 최댓값 세그먼트 트리를 이용해 각 쿼리를 O(log N)에 처리한다.

먼저 전체 코드를 제시하고, 각 전처리와 쿼리 처리 과정을 순서대로 설명한다.

class SegTree:
    def __init__(self, arr: List[int]):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n + 1)
        self.build(1, 0, self.n - 1, arr)

    def build(self, node_index: int, seg_left: int, seg_right: int, arr: List[int]):
        if seg_left == seg_right:
            self.tree[node_index] = arr[seg_left]
            return

        mid = (seg_left + seg_right) // 2
        self.build(node_index * 2, seg_left, mid, arr)
        self.build(node_index * 2 + 1, mid + 1, seg_right, arr)

        self.tree[node_index] = max(
            self.tree[node_index * 2], self.tree[node_index * 2 + 1]
        )

    def _query(
        self,
        node_index: int,
        seg_left: int,
        seg_right: int,
        qur_left: int,
        qur_right: int,
    ) -> int:
        if seg_right < qur_left or qur_right < seg_left:
            return 0

        if qur_left <= seg_left <= seg_right <= qur_right:
            return self.tree[node_index]

        mid = (seg_left + seg_right) // 2
        left = self._query(node_index * 2, seg_left, mid, qur_left, qur_right)
        right = self._query(node_index * 2 + 1, mid + 1, seg_right, qur_left, qur_right)

        return max(left, right)

    def query(self, left: int, right: int) -> int:
        if left > right:
            return 0
        return self._query(1, 0, self.n - 1, left, right)


class Solution:
    def maxActiveSectionsAfterTrade(
        self, s: str, queries: List[List[int]]
    ) -> List[int]:
        zeroes = []
        check = s.count("1")

        start = -1
        count = 0

        for i, v in enumerate(s):
            if v == "0":
                count += 1
                if start == -1:
                    start = i
            else:
                if count > 0:
                    zeroes.append((start, i - 1))
                    start = -1
                    count = 0

        if count > 0:
            zeroes.append((start, len(s) - 1))

        part_sum = [
            (zeroes[i][1] - zeroes[i][0]) + (zeroes[i + 1][1] - zeroes[i + 1][0]) + 2
            for i in range(len(zeroes) - 1)
        ]

        if len(part_sum) == 0:
            return [check] * len(queries)

        tree = SegTree(part_sum)

        # Return : cut inside, right index
        def search_start(arr: List[Tuple[int, int]], index: int) -> List[int]:
            left = 0
            right = len(arr)

            while left <= right:
                mid = (left + right) // 2

                if mid >= len(arr):
                    return [0, mid]

                if arr[mid][0] > index:
                    right = mid - 1
                elif arr[mid][1] < index:
                    left = mid + 1
                else:
                    return [arr[mid][1] - index + 1, mid + 1]

            return [0, left]

        def search_end(arr: List[Tuple[int, int]], index: int) -> List[int]:
            left = 0
            right = len(arr)

            while left <= right:
                mid = (left + right) // 2

                if mid >= len(arr):
                    return [0, mid - 1]

                if arr[mid][0] > index:
                    right = mid - 1
                elif arr[mid][1] < index:
                    left = mid + 1
                else:
                    return [index - arr[mid][0] + 1, mid - 1]

            return [0, right]

        ans = []

        for s, e in queries:
            start_dummy, start_index = search_start(zeroes, s)
            end_dummy, end_index = search_end(zeroes, e)

            if start_index - 2 == end_index:
                ans.append(check)
            elif start_index - 1 == end_index:
                if start_dummy != 0 and end_dummy != 0:
                    ans.append(check + start_dummy + end_dummy)
                else:
                    ans.append(check)
            else:
                if start_dummy > 0:
                    start_pos = start_dummy + (zeroes[start_index][1] - zeroes[start_index][0] + 1)
                else:
                    start_pos = 0
                if end_dummy > 0:
                    end_pos = end_dummy + (zeroes[end_index][1] - zeroes[end_index][0] + 1)
                else:
                    end_pos = 0

                middle = tree.query(start_index, end_index - 1)

                ans.append(max(start_pos, end_pos, middle) + check)

        return ans

1. 0이 반복되는 구간을 구한다.

zeroes = []
        check = s.count("1")

        start = -1
        count = 0

        for i, v in enumerate(s):
            if v == "0":
                count += 1
                if start == -1:
                    start = i
            else:
                if count > 0:
                    zeroes.append((start, i - 1))
                    start = -1
                    count = 0

        if count > 0:

• check에는 원래 문자열 전체의 '1' 개수를 저장한다. 트레이드는 쿼리 구간 내부에서만 일어나므로, 각 쿼리의 정답은 항상 check + 트레이드로 얻는 최대 증가량으로 계산할 수 있다.
• zeroes에는 문자열의 모든 최대 연속 0 구간을 (시작 인덱스, 끝 인덱스) 형태로 저장한다.
• 이 구간들은 시작 인덱스 기준으로 정렬된 상태이므로, 이후 쿼리의 양 끝이 어느 0 구간에 속하는지 이진 탐색으로 찾을 수 있다.

2. 미리 붙어있는 2개의 0의 합을 구한다.

        part_sum = [
            (zeroes[i][1] - zeroes[i][0]) + (zeroes[i + 1][1] - zeroes[i + 1][0]) + 2
            for i in range(len(zeroes) - 1)
        ]

• 서로 인접한 두 0 구간 zeroes[i], zeroes[i + 1] 사이에는 반드시 하나 이상의 '1'이 존재한다.
• 그 사이의 1 블록을 트레이드 대상으로 선택하면 최종적으로 새롭게 '1'이 되는 부분은 양쪽 0 구간이므로, 증가량은 두 0 구간의 길이 합이다.
• 따라서 part_sum[i]는 zeroes[i]와 zeroes[i + 1]을 이용한 트레이드의 증가량을 의미한다.
• 코드에서 각 구간 길이를 끝 - 시작 + 1로 계산하므로, 두 식의 마지막 + 2는 두 구간에 필요한 + 1을 한꺼번에 더한 것이다.

3. 세그먼트 트리를 만든다.

        if len(part_sum) == 0:
            return [check] * len(queries)

        tree = SegTree(part_sum)

• part_sum이 비어 있다는 것은 서로 다른 두 0 구간이 존재하지 않는다는 뜻이다. 이 경우 어떤 쿼리에서도 활성 구간 수를 늘리는 트레이드를 만들 수 없으므로 모든 답은 기존 '1' 개수인 check가 된다.
• 일반적인 쿼리에서는 쿼리 안에 완전히 포함된 여러 0 구간 중, 서로 인접한 두 구간의 길이 합의 최댓값을 반복해서 구해야 한다.
• 이는 part_sum의 특정 연속 범위에서 최댓값을 구하는 문제이므로 최댓값 세그먼트 트리를 만든다.
• 트리는 O(N)에 구축하고, 각 범위 최댓값은 O(log N)에 구할 수 있다.

세그먼트 트리 코드 ( 최댓값 )

class SegTree:
    def __init__(self, arr: List[int]):
        self.n = len(arr)
        self.tree = [0] * (4 * self.n + 1)
        self.build(1, 0, self.n - 1, arr)

    def build(self, node_index: int, seg_left: int, seg_right: int, arr: List[int]):
        if seg_left == seg_right:
            self.tree[node_index] = arr[seg_left]
            return

        mid = (seg_left + seg_right) // 2
        self.build(node_index * 2, seg_left, mid, arr)
        self.build(node_index * 2 + 1, mid + 1, seg_right, arr)

        self.tree[node_index] = max(
            self.tree[node_index * 2], self.tree[node_index * 2 + 1]
        )

    def _query(
        self,
        node_index: int,
        seg_left: int,
        seg_right: int,
        qur_left: int,
        qur_right: int,
    ) -> int:
        if seg_right < qur_left or qur_right < seg_left:
            return 0

        if qur_left <= seg_left <= seg_right <= qur_right:
            return self.tree[node_index]

        mid = (seg_left + seg_right) // 2
        left = self._query(node_index * 2, seg_left, mid, qur_left, qur_right)
        right = self._query(node_index * 2 + 1, mid + 1, seg_right, qur_left, qur_right)

        return max(left, right)

    def query(self, left: int, right: int) -> int:
        if left > right:
            return 0
        return self._query(1, 0, self.n - 1, left, right)

4. 이제 이진탐색을 준비한다.

zeroes가

[(1, 3), (5, 7), (9, 11), (13, 15)]

인 경우를 생각해보자.

쿼리가 [4, 12]라면 (5, 7)과 (9, 11)이 쿼리 안에 완전히 포함된다. 이처럼 완전히 포함된 0 구간끼리 만드는 후보는 part_sum의 범위 최댓값으로 구할 수 있다.

하지만 쿼리의 시작점이 2라면 첫 번째 0 구간 (1, 3) 전체가 아니라 (2, 3)만 쿼리에 포함된다. 이 경계 조각의 실제 길이는 2인데, 미리 계산한 part_sum에는 원래 구간 길이 3이 들어 있으므로 그대로 사용할 수 없다.

따라서 쿼리의 양 끝에서는 다음 정보를 별도로 구한다.

1. search_start
   • 시작점이 0 구간 안에 있으면, 쿼리에 포함되는 해당 구간의 오른쪽 조각 길이를 반환한다.
   • 함께 반환하는 인덱스는 그 조각 다음에 있는 첫 번째 완전한 0 구간의 인덱스이다.
2. search_end
   • 끝점이 0 구간 안에 있으면, 쿼리에 포함되는 해당 구간의 왼쪽 조각 길이를 반환한다.
   • 함께 반환하는 인덱스는 그 조각 이전에 있는 마지막 완전한 0 구간의 인덱스이다.

두 함수 모두 정렬된 zeroes에서 위치를 찾으므로 O(log N)에 동작한다.

 def search_start(arr: List[Tuple[int, int]], index: int) -> List[int]:
            left = 0
            right = len(arr)

            while left <= right:
                mid = (left + right) // 2

                if mid >= len(arr):
                    return [0, mid]

                if arr[mid][0] > index:
                    right = mid - 1
                elif arr[mid][1] < index:
                    left = mid + 1
                else:
                    return [arr[mid][1] - index + 1, mid + 1]

            return [0, left]

        def search_end(arr: List[Tuple[int, int]], index: int) -> List[int]:
            left = 0
            right = len(arr)

            while left <= right:
                mid = (left + right) // 2

                if mid >= len(arr):
                    return [0, mid - 1]

                if arr[mid][0] > index:
                    right = mid - 1
                elif arr[mid][1] < index:
                    left = mid + 1
                else:
                    return [index - arr[mid][0] + 1, mid - 1]

            return [0, right]

5. 쿼리를 계산한다.

• 각 쿼리 [s, e]에 대해 search_start, search_end로 경계에서 잘린 0 조각의 길이와 내부의 완전한 0 구간 범위를 구한다.
• 이후 가능한 후보 수에 따라 세 경우로 나눈다.

1. start_index - 2 == end_index
   • 쿼리 안에 트레이드에 사용할 두 0 조각이 존재하지 않는다.
   • 증가량은 0이므로 기존 '1' 개수인 check를 답에 넣는다.
2. start_index - 1 == end_index
   • 완전한 0 구간은 없고, 양쪽 경계에서 잘린 두 조각만 하나의 후보를 만들 수 있는 경우이다.
   • 두 경계가 모두 실제 0 조각일 때만 start_dummy + end_dummy만큼 증가시킬 수 있다.
3. 그 외의 경우
   • 왼쪽 경계 조각과 바로 다음 완전한 0 구간을 합친 후보가 start_pos이다.
   • 오른쪽 경계 조각과 바로 이전 완전한 0 구간을 합친 후보가 end_pos이다.
   • 쿼리 안에 완전히 포함된 0 구간끼리의 후보 최댓값은 세그먼트 트리에서 middle로 구한다.
   • 세 값 중 최댓값이 해당 쿼리에서 얻을 수 있는 최대 증가량이다.

마지막으로 최대 증가량을 원래 문자열 전체의 '1' 개수 check에 더해 정답을 만든다. 두 번의 이진 탐색과 한 번의 세그먼트 트리 조회가 필요하므로 쿼리 하나당 O(log N)이다.

        ans = []

        for s, e in queries:
            start_dummy, start_index = search_start(zeroes, s)
            end_dummy, end_index = search_end(zeroes, e)

            if start_index - 2 == end_index:
                ans.append(check)
            elif start_index - 1 == end_index:
                if start_dummy != 0 and end_dummy != 0:
                    ans.append(check + start_dummy + end_dummy)
                else:
                    ans.append(check)
            else:
                if start_dummy > 0:
                    start_pos = start_dummy + (zeroes[start_index][1] - zeroes[start_index][0] + 1)
                else:
                    start_pos = 0
                if end_dummy > 0:
                    end_pos = end_dummy + (zeroes[end_index][1] - zeroes[end_index][0] + 1)
                else:
                    end_pos = 0

                middle = tree.query(start_index, end_index - 1)

                ans.append(max(start_pos, end_pos, middle) + check)

        return ans

총 시간복잡도 : O(N + Q Log N)

• N : 문자열 s의 길이
• Q : 쿼리의 개수

0 구간 추출, part_sum 생성, 세그먼트 트리 구축에는 모두 합쳐 O(N)이 필요하다. 각 쿼리는 이진 탐색과 세그먼트 트리 조회로 O(log N)에 처리되므로 총 시간복잡도는 O(N + Q log N)이다.

추가 공간복잡도는 zeroes, part_sum, 세그먼트 트리에 의해 O(N)이다.

총평

• 핵심 아이디어는 연속한 두 0 구간의 길이 합을 최대화하는 것이지만, 쿼리의 양쪽 경계에서 0 구간이 잘리는 경우까지 따로 처리해야 해서 구현 난도가 크게 올라간 문제였다.
• 이진 탐색으로 양쪽 경계 후보를 구하고, 완전히 포함되는 내부 후보는 세그먼트 트리로 조회하도록 역할을 나누는 것이 풀이의 핵심이다.
• 부분합, 이진 탐색, 세그먼트 트리를 한 문제 안에서 정확히 결합해야 하므로 체감 난도가 상당히 높았다. 어우 어려워.