[리트코드 leetcode] 2575. Find the Divisibility Array of a String (파이썬/Python)

 

목차

개요

Find the Divisibility Array of a String - LeetCode

어떤 수가 주어지면 그 수를 가장 높은 자리부터 하나씩 늘려가며 수를 만들고 그 수가 m에 나눠지는지에 따라 div 배열을 만들어 반환하기.

풀이

class Solution:
    def divisibilityArray(self, word: str, m: int) -> List[int]:
        ans = []
        n = len(word)
        i = 1
        while i <= n:
            curr_num = int(word[:i])
            if curr_num % m:
                ans.append(0)
            else:
                ans.append(1)
            i += 1
        
        return ans

문제 설명에 충실한 코드. 그러나 이렇게 풀면 시간 초과를 면할 수 없다. 

이때 접근가능한 방법 중 하나는 나머지 법칙을 활용하는 것이다.

대충 이런 게 있다. 사칙연산에 대해서 전부 성립한다. 나눗셈의 경우에는 조금 특별하게 식을 계산하는데, 자세한 건 검색!
이런 나머지 법칙을 활용하게 되는 경우는 나머지를 찾아야 하는 케이스에 대해서, 수가 너무 커서  메모리나 시간에 문제가 있을 때이다.

상세한 수식은 이렇게 쓴다. 덧셈에 대한 나머지 법칙, 그 안에 곱셈에 대한 나머지 법칙이 들어있는 구조. 

다른 사람의 풀이를 보니 더 간단하게 되어있던데 그 기반은 나머지 법칙이란 것만 알면 될 것 같다. 

코드

class Solution:
    def divisibilityArray(self, word: str, m: int) -> List[int]:
        ans = []
        n = len(word)
        curr = 0
        for i in word:
            prev_divisible = ((curr % m) * (10 % m)) % m
            curr = (prev_divisible + (int(i) % m)) % m
            if curr:
                ans.append(0)
            else:
                ans.append(1)

        
        return ans