Python으로 이진 문자열을 '1' 개수가 같은 세 부분으로 나누는 방법의 수 구하기

문제 정의

이진 문자열 s가 주어졌을 때, 이를 세 개의 비어 있지 않은 부분 문자열 s1, s2, s3로 분할한다고 가정해 봅시다. 이때 s1, s2, s3를 순서대로 이어 붙이면 원래 문자열 s와 같아야 합니다(s1 + s2 + s3 = s). 우리가 구해야 할 것은 세 부분 문자열에 포함된 문자 '1'의 개수가 모두 동일하도록 s를 나누는 방법의 수입니다. 답은 매우 커질 수 있으므로 10^9+7로 나눈 나머지를 반환해야 합니다.

예시

입력이 s = "11101011"이라면 출력은 2가 됩니다. 다음 두 가지 방식으로 나눌 수 있기 때문입니다.

"11 | 1010 | 11"
"11 | 101 | 011"

해결 접근 방식

이 문제는 다음 단계에 따라 해결할 수 있습니다.

먼저 문자열 s에 포함된 '1'의 총 개수를 셉니다(count).
m := 10^9 + 7 (모듈러 값)
ans := 크기가 2인 배열, 0으로 초기화
'1'의 개수가 3으로 나누어 떨어지지 않으면 세 부분이 같은 개수를 가질 수 없으므로 0을 반환합니다.
'1'의 개수가 0이라면, 문자열 내에서 두 개의 경계 위치를 선택하는 조합, 즉 C(n-1, 2)를 m으로 나눈 나머지를 반환합니다.
left := 0, right := len(s) - 1로 초기화하고, 누적 변수 cum_s := 0, cum_e := 0으로 설정합니다.
cum_s 또는 cum_e가 count//3 이하인 동안 다음을 반복합니다.
- s[left]가 "1"이면 cum_s를 1 증가시킵니다.
- s[right]가 "1"이면 cum_e를 1 증가시킵니다.
- cum_s가 count//3과 같으면 ans[0]을 1 증가시킵니다.
- cum_e가 count//3과 같으면 ans[1]을 1 증가시킵니다.
- left는 1 증가, right는 1 감소시킵니다.
최종적으로 (ans[0] * ans[1]) % m을 반환합니다.

여기서 핵심 아이디어는 다음과 같습니다. 왼쪽에서부터 첫 번째 구간이 count//3개의 '1'을 포함하는 지점의 후보 개수(ans[0])와, 오른쪽에서부터 세 번째 구간이 count//3개의 '1'을 포함하는 지점의 후보 개수(ans[1])를 각각 구한 뒤 두 값을 곱하면, 가운데 구간은 자동으로 같은 개수의 '1'을 갖게 되므로 전체 분할 방법의 수가 계산됩니다.

구현 예제

def solve(s):
   count = s.count("1")
   m = 10**9 + 7
   ans = [0, 0]
   if count % 3 != 0:
      return 0
   elif count == 0:
      return comb(len(s)-1,2) % m
   left = 0
   right = len(s)-1
   cum_s = 0
   cum_e = 0
   while(cum_s <= count//3 or cum_e <= count//3):
      if s[left] == "1":
         cum_s += 1
      if s[right] == "1":
         cum_e += 1
      if cum_s == count//3:
         ans[0] += 1
      if cum_e == count//3:
         ans[1] += 1
      left += 1
      right -= 1
   return (ans[0]*ans[1]) % m

s = "11101011"
print(solve(s))

입력

"11101011"