1018. Binary Prefix Divisible By 5
https://leetcode.com/problems/binary-prefix-divisible-by-5/
0과 1로만 이루어진 배열이 주어질 때, 0 ~ x번째 인덱스까지 원소를 쭉 이어서 이진수를 만든다.
그 수를 십진법으로 바꾸었을 때, 5로 나누어지는지를 확인하는 문제이다.
마지막 원소까지 반복한 뒤, 결과를 리스트에 저장해 리턴하면 된다.
처음에는 다음과 같이 bit 연산을 통해 결과를 구하려고 했다.
int num = nums[0];
for(int i = 1; i < nums.length; i++) {
num = num << 1;
num += nums[i];
}하지만 인풋으로 주어지는 배열의 크기가 10^5가 넘어가기 때문에 너무나 당연하게도 오버 플로우가 발생한다..
int 대신 long을 사용하더라도 똑같이 오버 플로우가 발생해서 다른 방법을 사용해야 했다.
그래서 새롭게 접근한 방법은 5로 나누어 떨어지는 수의 조건이 무엇일까였다.
5로 나눴을 때, 나머지가 0이 되려면 1의 자리가 0 또는 5가 되어야 한다. 이해가 안 된다면 구구단 5단을 외워보자..
따라서 위의 방법에서 1의 자리만 남겨두고 계속해서 연산을 수행하면 정답을 쉽게 구할 수 있다!
class Solution {
public List<Boolean> prefixesDivBy5(int[] nums) {
List<Boolean> isDiv = new ArrayList<>();
int num = nums[0];
isDiv.add(num % 5 == 0);
for(int i=1;i<nums.length;i++){
num = (num * 2) % 10;
num += nums[i];
isDiv.add(num % 5 == 0);
}
return isDiv;
}
}https://leetcode.com/submissions/detail/597182415/
https://github.com/sorious77/LeetCode/blob/main/code/1018.java
🔔