(C++) - LeetCode (easy) 1018. Binary Prefix Divisible By 5

https://leetcode.com/problems/binary-prefix-divisible-by-5/description/

LeetCode - The World's Leading Online Programming Learning Platform

구현 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

정답 ans와 현황 cur를 선언해준 후 적절히 초기화해줍니다.

📔 풀이과정

nums의 길이가 10^5(10만)이므로 매번 전체 십진수를 계산해 5로 나누어떨어지는 방법으로는 overflow가 나게 됩니다. 따라서 나머지 연산의 특징으로 overflow를 피해 구현하면 됩니다. 

nums의 원소를 순회하며 다음을 수행합니다.

1. 현재 자리에서 cur에 이전 값(cur) * 2 를 지나왔으므로 더해주고 현재 자리 n값을 더해줍니다.

2. 그 후 5로 나눈 나머지를 cur에 저장합니다. ((계산값 % 5) % 5) % 5 .... = 계산값 % 5이므로 해당 방식이 성립합니다.

3. ans에는 나머지 cur가 0인지 여부만 push_back해주면 됩니다.

📔 정답 출력 | 반환

ans를 반환합니다.

---

📕 Code

📔 C++

class Solution {
public:
    vector<bool> prefixesDivBy5(vector<int>& nums) {
        vector <bool> ans;
        int cur = 0;
        for(auto n : nums) {
            cur = (cur * 2 + n) % 5;
            ans.push_back(!cur);
        }
        return ans;
    }
};

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.