Python으로 이진 문자열에서 1로만 이루어진 부분 문자열 개수 세기

이진 문자열 s가 주어졌을 때, "1"로만 이루어진 부분 문자열의 개수를 구하는 문제를 살펴보겠습니다. 만약 답이 너무 크다면 결과를 10^9+7로 나눈 나머지를 반환하면 됩니다.

문제 이해하기

예를 들어 입력이 s = "100111"이라면 출력은 7이 됩니다. "1"로만 이루어진 부분 문자열은 ["1", "1", "1", "1", "11", "11", "111"]로 총 7개이기 때문입니다.

해결 접근 방법

이 문제는 각 위치에서 끝나는 "1" 부분 문자열의 개수를 누적하는 방식으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 변수 a와 count를 0으로 초기화합니다.
• 인덱스 i를 0부터 문자열 길이 - 1까지 순회합니다.
• s[i]가 "0"이라면 a를 0으로 초기화합니다. (연속된 1이 끊김)
• 그렇지 않으면 a를 1 증가시키고, count에 a를 더합니다.
• 순회가 끝나면 count를 반환합니다.

여기서 a는 현재 위치에서 끝나는 연속된 "1"의 길이를 의미하며, 곧 해당 위치에서 끝나는 "1" 부분 문자열의 개수와 같습니다. 따라서 전체 시간 복잡도는 O(n)으로 매우 효율적입니다.

구현 예제

더 나은 이해를 위해 다음 Python 구현을 살펴보겠습니다.

def solve(s):
    a = 0
    count = 0
    for i in range(len(s)):
        if s[i] == "0":
            a = 0
        else:
            a += 1
            count += a
    return count

s = "100111"
print(solve(s))

입력

"100111"

출력

7

마무리

이 알고리즘은 문자열을 한 번만 순회하면서 연속된 "1"의 개수를 추적하기 때문에 시간 복잡도 O(n), 공간 복잡도 O(1)로 문제를 해결할 수 있습니다. 연속된 요소의 누적 개수를 활용하는 이 패턴은 다양한 문자열 및 배열 문제에 응용할 수 있으니 잘 기억해 두면 유용합니다.