Leetcode 1018. Binary Prefix Divisible By 5

You are given a binary array nums (0-indexed).

We define x_i as the number whose binary representation is the subarray nums[0..i] (from most-significant-bit to least-significant-bit).

• For example, if nums = [1,0,1], then x₀ = 1, x₁ = 2, and x₂ = 5.

Return an array of booleans answer where answer[i] is true if x_i is divisible by 5.

 

Constraints:

• 1 <= nums.length <= 10⁵
• nums[i] is 0 or 1.

2진수 숫자의 정수 배열이 있다.

nums[0...i]의 2진수를 10진수 숫자 x_i로 정의한다(최상위 비트부터 최하위 비트까지).

• 예를 들어, 만약 nums = [1,0,1], 그러면 x₀ = 1, x₁ = 2, and x₂ = 5.

만약 x_i가 5로 나뉘면 참인 answer이라는 boolean 배열을 반환하라.

 

Example 1:

Input: nums = [0,1,1]

Output: [true,false,false]

Explanation: The input numbers in binary are 0, 01, 011; which are 0, 1, and 3 in base-10. Only the first number is

divisible by 5, so answer[0] is true.

 

0 -> 0 / 5 = 0 그러므로 true.

01 -> 1 / 5는 정확히 나눠지지 않으므로 false.

011 -> 3 / 5도 정확히 나눠지지 않으므로 false.

 

Example 2:

Input: nums = [1,1,1]

Output: [false,false,false]

 

Example 3:

Input: nums = [0,1,1,1,1,1]

Output: [true,false,false,false,true,false]

 

Example 4:

Input: nums = [1,1,1,0,1]

Output: [false,false,false,false,false]

 

실패 알고리즘

class Solution {
    public List<Boolean> prefixesDivBy5(int[] nums) {
        List<Boolean> list = new ArrayList<Boolean>();
        long currentNum = 0;
        
        for (int num : nums) {
            currentNum += num;
            
            if (currentNum % 5 == 0) {
                list.add(true);
            } else {
                list.add(false);
            }
            
            currentNum *= 2;
 
        }
        
        return list;
    }
}

원리

예시: [0. 1, 1]

 

nums[0] = 0, currentNum = 0

currentNum에 nums[0]를 더한다 -> currentNum += 0

currentNum % 5의 결괏값이 0이면 true 아니면 false를 list에 넣는다 -> list.add(true)

currentNum를 2배 시킨다 -> currentNum *= 2 

 

nums[1] = 1, currentNum = 0

currentNum에 nums[1]를 더한다 -> currentNum += 1

currentNum % 5의 결괏값이 0이면 true 아니면 false를 list에 넣는다 -> list.add(false)

currentNum를 2배 시킨다 -> currentNum *= 2 

 

nums[2] = 1, currentNum = 2

currentNum에 nums[2]를 더한다 -> currentNum += 1

currentNum % 5의 결괏값이 0이면 true 아니면 false를 list에 넣는다 -> list.add(false)

currentNum를 2배 시킨다 -> currentNum *= 2

 

이 방법은 성공되긴 된다 하지만 제출 시 테스트에서 실패한다 이유는 overflow 현상이다.

7번째 테스트의 입력값은 [1,0,0,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,1,0,1,0,0,0,0,1,1,0,1,0,0,0,1].

정확히 32번째에서 실패한다 그 이유는 정수의 최댓값은 2^31이고(양수의 최댓값) 주어진 입력값은 2^38이기 때문이다.

그래서 long으로 할당 할 수 있는 최댓값을 2^63까지 올렸지만 역시나 overflow로 10번째에서 틀렸다.

일단 Constraints를 제대로 안 읽었다 num의 크기가 최대 10^5이면 이 숫자는 long으로는 택도 없다. 왜냐하면 long에 할당 가능한 최대 값인 2^63는 입력의 최댓값으로 나타낼 수 있는 2^10000 값을 저장할 수 없다. 

 

 

그래서 유튜브로 해답을 찾았다. 아니 이럴 수가 한 줄만 있었으면 푸는 것이었다.

바로 currentNum %= 5 이 한 줄만 넣으면 된 것이다.

변경 코드: currentNum *= 2에서 currentNum <<= 1로 바꿨다. 둘 다 차이는 없지만 비트 연산이 더 빠르기때문.

 

성공 코드

class Solution {
    public List<Boolean> prefixesDivBy5(int[] nums) {
        List<Boolean> list = new ArrayList<Boolean>();
        int currentNum = 0;
        
        for (int num : nums) {
            currentNum += num;
            
            if (currentNum % 5 == 0) {
                list.add(true);
            } else {
                list.add(false);
            }
            
           currentNum <<= 1;
            currentNum %= 5;
        }
        
        return list;
    }
}

N = nums 크기

시간 복잡도: O(N)

공간 복잡도: O(N)

 

currentNum를 줄여야 overflow 에러를 방지하는 건 인지했지만 currentNum % 5 연산을 하면 그다음 숫자에 영향을 미칠까 봐 반직관적이었다. 하지만 실제 예시를 들어 % 5 연산 후 currentNum 값을 보고 알고리즘에 대한 확신이 생겼다.

 

5와 95가 섞인 예시

[0, 1, 0, 1, 1, 1, 1, 1] => 0, 1, 2, 5, 11, 23, 47, 95
    

2진수	실제 값	currentNum %= 5 후 currentNum 값
0	0	0 % 5 = 0
01	1	1 % 5 = 1
010	2	2 % 5 = 2
0101	5	5 % 5 = 0
01011	11	1 % 5 = 1
010111	23	3 % 5 = 3
0101111	47	7 % 5 = 7
01011111	95	15 % 5 = 0

패턴: 5 다음 11이 와야 하지만 5 다음 1이 돼도 사실상 0 + 1이나 10 + 1은 동일하다 왜냐하면 맨 뒷자리수가 0이거나 5인지만 중요하고 맨 뒷자리수 외에 숫자는 상관없다.