1573. Number of Ways to Split a String

문제

class Solution:
    def numWays(self, s: str) -> int:
        countOne = 0
        for num in s:
            if num == "1":
                countOne += 1
        
        if countOne % 3 != 0: return 0
        if countOne == 0: return ((len(s) - 1) * (len(s) - 2) // 2) % ( 10 ** 9 + 7 )
        
        
        needOne = countOne // 3
        
        countOne = 0
        
        firstToSecond  = 0
        secondToThird  = 0
        
        for num in s:
            if num == "1":
                countOne += 1
            if num == "0" and countOne == needOne:
                firstToSecond += 1
            if num == "0" and countOne == needOne * 2:
                secondToThird += 1
        
        
        return ((firstToSecond + 1) * (secondToThird+1)) % ( 10 ** 9 + 7 )

문제 간단 설명

0과 1로 이루어진 string을 3분할 했을때 각 각 substring의 합이 서로 같을 수 있는 substring 조합의 갯수를 구하는 문제 입니다.

문제 해결 방법

1. 일단 1의 갯수를 구해서 3으로 나누어 떨어지지 않으면 합이 같은 3개의 substring으로 나눌수가 없다.

2. 그리고 1의 갯수가 없을때는 0만으로 이루어진 string에서 substring 3개로 나누는 조합을 생각해야 합니다.
   조합 만드는 방식

   1. 0000000 이런식의 숫자가 있으면 칸막이를 세운다고 생각하면 쉽습니다.
   2. 0|0000|00 이렇게 칸막이를 세운다면 칸막이를 세울 수 있는 경우의 수를 생각해봅시다.
   3. 칸막이를 세울 수 있는 곳은 길이가 7인 string에서는 6곳 입니다. 0|0|0|0|0|0|0
   4. 그럼 우리는 칸막이를 2개를 세워야 3개의 substring을 만들 수 있으므로 6C2의 경우의 수를 가지게 됩니다.
   5. 그럼 일반화 하면 n의 길이를 가지는 string이면 n-1C2를 리턴하면 됩니다.

3. 그리고 1의 갯수가 0보다 클때 경우의 수 생각하기

   1. 그러면 우리는 칸막이를 어디에 세울지 생각해야 합니다.
   2. 0100010001000 이런식의 배열이라면 모든 substring의 합이 같아야 하므로 1은 각각 같은 수 만큼 가지게 해야합니다.
   3. 그럼 칸막이는 첫번째 string에서 마지막 1과 두번째 string에서 첫 1사이에 설치해야 하고 예를 들면 010|0010001000 이런식으로
   4. 두번째 string의 마지막 1과 세번째 string에 첫 1사이에 설치할 수 있습니다.
   5. 그럼 칸막이를 칠 수 있는 경우의 수는 어떻게 될까요?
   6. 첫번째 string의 마지막 1과 두번째 string의 첫번째 1사이에 위치하는 0의 갯수로 정할 수 있습니다. 0의 갯수가 0이라면 1가지 갯수가 2개라면 3가지
   7. 그래서 칸막이의 경우의 수를 각 각 구해서 곱하면 경우의 수를 완성 할 수 있습니다.