1. 문제 소개

1018. Binary Prefix Divisible By 5

2. 나의 풀이

배열을 순회하면서 이진수를 십진수로 변환하고 이를 5로 바꾼 나머지를 생각해 풀었다.

class Solution:
    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:
        n = len(nums)                           # 입력 길이 (정보용)
        cur = 0                                 # 현재 prefix의 mod 5 값만 추적
        ans = list()                            # 각 prefix가 나누어떨어지는지 저장

        for num in nums:                        # nums의 비트를 순차적으로 prefix에 추가
            cur = (cur * 2 + num) % 5           # 이진수 왼쪽 shift 후 num 추가, 그리고 mod 5
            ans.append(cur == 0)                # 현재 prefix가 5로 나누어지면 True

        return ans                              # prefix들에 대한 결과 리스트 반환

3. 다른 풀이

class Solution:
    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:
        answer = list()                         # 각 prefix가 5로 나누어 떨어지는지 저장할 리스트
        prefix = 0                              # 현재 prefix의 값(정확히는 mod 5만 유지)

        for num in nums:                        # nums의 비트를 순서대로 prefix에 추가
            prefix = ((prefix << 1) + num) % 5  # 이진수 확장: prefix*2 + num, 그리고 mod 5 유지
            answer.append(prefix == 0)          # mod 5가 0이면 현재 prefix는 5로 나누어짐(True)

        return answer                           # 모든 prefix의 결과(Boolean) 리스트 반환

4. 마무리

처음에는 cur에 계속 더하는 방식으로 풀어서 틀렷었다.
그러나 갱신하는 방식으로 바꿔서 풀 수 있었다.