Python으로 1로만 이루어진 부분 문자열 개수 구하기

이진 문자열(binary string) s가 주어졌을 때, 모든 문자가 1로만 이루어진 부분 문자열(substring)의 개수를 구하는 문제입니다. 답이 매우 커질 수 있기 때문에 결과는 10^9 + 7로 나눈 나머지(modulo)를 반환해야 합니다.

예를 들어 입력이 s = "1011010"이라면 출력은 5가 됩니다. 그 이유는 다음과 같습니다.

• "1" → 4번 등장
• "11" → 1번 등장

문제 해결 접근 방법

핵심 아이디어는 간단합니다. 문자열을 '0'을 기준으로 분할하면, 연속된 1로만 이루어진 덩어리(블록)들이 남게 됩니다. 길이가 n인 연속된 1 블록 안에서 만들 수 있는 부분 문자열의 개수는 조합 공식에 따라 n × (n + 1) / 2입니다.

예를 들어 "111"이라는 블록이 있다면, 부분 문자열은 "111", "11"(2개 위치), "1"(3개 위치)로 총 6개이며, 이는 3 × 4 / 2 = 6과 일치합니다.

알고리즘 단계

• m := 10^9 + 7 (모듈러 값)
• result := 0 (결과 초기화)
• div := 이진 문자열을 '0'을 기준으로 분할
• div의 각 요소 x에 대해 다음을 수행:
  • x가 비어 있으면 다음 반복으로 건너뜀
  • result := result + (x의 길이 × (x의 길이 + 1)) // 2
• result mod m을 반환

구현 예제

def solve(s):
    m = 10**9+7
    result = 0
    for x in s.split('0'):
        if not x: continue
        result += (len(x)*(len(x)+1)) // 2
    return result % m

s = "1011010"
print(solve(s))

입력

"1011010"

출력

5

복잡도 분석

이 알고리즘은 문자열을 한 번 순회하며 분할된 각 블록의 길이만 계산하므로 시간 복잡도는 O(n), 추가 공간 복잡도 역시 O(n)입니다. split() 대신 문자열을 직접 순회하면서 연속된 1의 개수를 세는 방식으로 구현하면 공간 복잡도를 O(1)까지 줄일 수 있습니다.