[Leetcode][2222][Medium] Number of Ways to Select Buildings

문제

2222번 문제 링크

간단한 DP 문제이다.
요약하면, 0과 1로 구성된 문자열에서 010 또는 101 경우의 수를 찾는 문제이다.
조건이 3 <= s.length <= 10^5 이므로 시간복잡도는 O(N)이 되도록 접근하였다.

풀이

처음에는 양 끝의 수가 같은 경우, 안의 숫자의 갯수를 구하려고 했으나,
가운데 수를 정하고 양 끝의 수의 갯수를 정하는 방법이 더욱 간단한 접근이었다.
Loop를 돌면서 가운데 수가 1이면 양 옆의 0의 갯수의 곱이 가운데 1의 010 가짓수가 된다.

먼저, 미리 각 index 지점 까지의 0과 1의 갯수를 계산해 놓는다.
그리고 n번 째가 0이라 할 때, n-1번 째 까지의 1과 n+1번 째 부터 끝까지의 1의 갯수의 곱이
n번 째의 010 가짓수가 된다.

def numberOfWays(self, s: str) -> int:
        result = 0

        l = []

        c0 = 0
        c1 = 0
        for c in s:
            if c == '0':
                c0 += 1
            else:
                c1 += 1
            l.append((c0, c1))

        t0 = c0
        t1 = c1

        for i in range(1, len(s)-1):
            if s[i] == '0':
                result += l[i-1][1] * (t1 - l[i][1])
            else:
                result += l[i-1][0] * (t0 - l[i][0])

        return result

회고

1. 알고리즘은 많이 풀어보면 감이 온다.
2. 아이디어, 즉 접근법이 정말 중요하다.
3. 은근 개발할 때 도움도 많이 되는듯.