파이썬으로 '0 개수 × 2 ≤ 1 개수 × 3' 조건을 만족하는 최장 부분 문자열 길이 구하기

문자열과 정수 k가 주어졌다고 가정해 봅시다. 원본 문자열을 k번 반복하여 새로운 문자열을 만들고, 이 새로운 문자열 안에서 “부분 문자열에 포함된 0의 개수 × 2 ≤ 부분 문자열에 포함된 1의 개수 × 3” 조건을 만족하는 부분 문자열의 길이를 찾는 것이 우리의 과제입니다.

예를 들어 k = 2, input_str = '0101011'이 입력으로 주어지면 출력은 14가 됩니다.

원본 문자열의 길이는 7이므로, 이를 2번 반복해 만든 새로운 문자열은 01010110101011입니다. 이 문자열에는 0이 6개, 1이 8개 포함되어 있으며, 2 × 6 = 12 ≤ 3 × 8 = 24이므로 조건을 만족합니다. 따라서 가장 긴 부분 문자열은 문자열 전체이고, 그 길이는 14입니다.

접근 방법

이 문제는 누적 합(prefix sum)과 정렬·이진 탐색을 활용해 효율적으로 해결할 수 있습니다. 각 위치에서의 가중치 누적 값을 계산한 뒤, 조건을 만족하는 가장 긴 구간을 찾아내는 방식입니다.

알고리즘 단계

str_len := input_str의 길이
list_a := 크기가 (str_len + 1)인 리스트를 0으로 초기화
list_b := 크기가 (str_len + 1)인 리스트를 0으로 초기화
list_b[0] := (0, 0) 쌍 저장
i를 0부터 str_len까지 반복:
- list_a[i + 1] := list_a[i] − 3 × (input_str[i]가 '1'이면 1, 아니면 0) + 2 × (input_str[i]가 '0'이면 1, 아니면 0)
- list_b[i + 1] := (list_a[i + 1], i + 1) 쌍 저장
list_b를 정렬
temp_list := 크기가 (str_len + 1)인 리스트를 0으로 초기화
temp_list[0] := list_b[0][1]
i를 0부터 str_len까지 반복:
- temp_list[i + 1] = max(temp_list[i], list_b[i + 1][1])
res := 0
i를 0부터 str_len까지 반복:
- tmp := list_b[0][0] − list_a[i]
- 만약 list_a[str_len] ≤ 0이면:
  - a := k − 1
  - tmp + list_a[str_len] × a > 0이면 다음 반복으로 건너뜀
- 그렇지 않고 tmp > 0이면 다음 반복으로 건너뜀
- 그 외의 경우:
  - a := min(k − 1, ⌊−tmp / list_a[str_len]⌋)
- v := a × list_a[str_len] − list_a[i]
- b := (−v + 1, 0) 쌍이 정렬 순서를 유지한 채 삽입될 수 있는 list_b의 위치 − 1
- res := max(res, temp_list[b] − i + a × str_len)
res 반환

구현 예제

다음 구현 예제를 통해 더 잘 이해해 봅시다.

from bisect import bisect_left

def solve(k, input_str):
    str_len = len(input_str)
    list_a = [0] * (str_len + 1)
    list_b = [0] * (str_len + 1)
    list_b[0] = (0, 0)

    for i in range(str_len):
        list_a[i + 1] = list_a[i] - 3 * (input_str[i] == '1') + 2 * (input_str[i] == '0')
        list_b[i + 1] = (list_a[i + 1], i + 1)

    list_b.sort()
    temp_list = [0] * (str_len + 1)
    temp_list[0] = list_b[0][1]

    for i in range(str_len):
        temp_list[i + 1] = max(temp_list[i], list_b[i + 1][1])

    res = 0
    for i in range(str_len):
        tmp = list_b[0][0] - list_a[i]
        if list_a[str_len] <= 0:
            a = k - 1
            if tmp + list_a[str_len] * a > 0:
                continue
        elif tmp > 0:
            continue
        else:
            a = min(k - 1, -tmp // list_a[str_len])

        v = a * list_a[str_len] - list_a[i]
        b = bisect_left(list_b, (-v + 1, 0)) - 1
        res = max(res, temp_list[b] - i + a * str_len)

    return res

print(solve(2, '0101011'))

입력

2, '0101011'

출력

마무리

이 알고리즘은 문자열의 각 문자에 가중치(1은 −3, 0은 +2)를 부여해 누적 합을 계산하고, 정렬된 값과 이진 탐색(bisect_left)을 활용해 조건을 만족하는 최장 구간을 효율적으로 찾습니다. 시간 복잡도는 O(n log n)으로, 문자열이 여러 번 반복되는 경우에도 빠르게 답을 구할 수 있다는 장점이 있습니다.