1. 문제 소개

3461. Check If Digits Are Equal in String After Operations I

2. 나의 풀이법

Easy난이도 문제였기에 쉬웠다.
간단한 반복문을 사용해서 문제를 풀었다.
그러나 각 단계별로 반복문을 사용해 시간복잡도가 $O(n^2)$이어서 느리게 풀리는 것 같다.

class Solution:
    def hasSameDigits(self, s: str) -> bool:
        while len(s) > 2:
            temp = ""
            for i in range(len(s) - 1):
                digit = (int(s[i]) + int(s[i+1])) % 10
                temp += str(digit)
            s = temp
        if s[0] == s[1]:
            return True
        else:
            return False

3. 다른 풀이법

인접한 두 수의 합을 구하는 것이 이항계수를 구하는 것과 방식이 같다.
이 경우 시간복잡도는 $O(n)$으로 줄어든다.

class Solution:
    def hasSameDigits(self, s: str) -> bool:
        s = [int(digits) for digits in s]
        n = len(s)
        binomial_coeff = [1] * (n - 1)
        # recursive definition of the coefficients
        for i in range(1, n - 1):
            binomial_coeff[i] = binomial_coeff[i-1] * (n-2-i+1) // i
        
        left = sum([digit*coeff for digit, coeff in zip(s[:-1], binomial_coeff)]) % 10
        right = sum([digit*coeff for digit, coeff in zip(s[1:], binomial_coeff)]) % 10
        return left == right

4. 결론

역시 코딩은 아이디어 싸움이다.