1. 문제 소개

1513. Number of Substrings With Only 1s

2. 나의 풀이

문제의 힌트를 보고 어떻게 푸는 지 알았다.
Count number of 1s in each consecutive-1 group. For a group with n consecutive 1s, the total contribution of it to the final answer is (n + 1) * n // 2.
연속된 1을 찾아내 이를 $\frac{n(n+1)}{2}$로 더하는 방식으로 풀었다.
마지막으로 MOD를 하면 완성이었다.
시간복잡도는 $O(n)$이다.

class Solution:
    def numSub(self, s: str) -> int:
        n = len(s)               # 문자열 길이 저장
        k = 0                    # 현재 연속된 '1'의 길이를 저장하는 카운터
        MOD = 10 ** 9 + 7        # 모듈러 연산 상수

        ans = 0                  # 최종 답을 누적할 변수
        for i in range(n):       # 문자열을 왼쪽에서 오른쪽으로 한 번 순회
            if s[i] == "0":      # '0'이 등장하면 현재까지의 연속된 '1' 구간 종료
                ans += (k * (k + 1) // 2) % MOD   # 길이 k의 구간에서 생기는 부분 문자열 수를 더함
                k = 0            # 연속된 '1' 카운터 초기화
            else:
                k += 1           # '1'이면 연속 구간 길이를 늘림

        ans += (k * (k + 1) // 2) % MOD  # 문자열 끝이 '1'일 경우 마지막 구간을 처리

        return ans               # 최종 결과 반환

3. 다른 풀이

빠르면서도 색다른 풀이는 주어진 문자열을 0을 기준으로 나눠 1만 세는 방식이었다.
이 또한 시간복잡도가 $O(n)$이지만 조건문이나 인덱스 처리가 없어 빠르다.

class Solution:
    def numSub(self, s: str) -> int:
        cnt = 0
        # 문자열을 '0'을 기준으로 분리한다.
        # 예: "111011" → ["111", "11"]
        # 이 과정은 O(n)에서 수행되며, 내부는 C로 최적화됨.
        for part in s.split('0'):
            n = len(part)            # 연속된 '1' 덩어리의 길이 L
            cnt += n*(n+1)           # L*(L+1)  (뒤에서 //2로 한 번에 나눌 예정)

        # 모든 덩어리의 L*(L+1)/2 합을 구한 뒤 모듈러 적용
        return (cnt // 2) % (10**9 + 7)

4. 결론

오늘은 내 힘으로 풀어서 기분이 좋다.