[LeetCode] 1018. Binary Prefix Divisible By 5 Solution in C++

안녕하세요. BlockDMask 입니다.

오늘부터는 LeetCode라는 알고리즘 문제풀이 사이트의 문제를 풀어보려고 합니다.

이 우리나라에서는 백준 사이트가 유명하긴하지만 세계적으로 보면 LeetCode와 hackerrank사이트가 유명하고, 특히나 미국에서는 LeetCode 알고리즘 사이트 사용수가  압도적으로 많습니다.

구글이나 그런 외국계 기업을 목표로 하시는 분들은 LeetCode 문제를 푸는걸 추천 드립니다.

1. Title

---

Title : 1018. Binary Prefix Divisible By 5 Solution in C++

Category : Weekly Contest 130   

Level : Easy  

Language : C++, C++11/14   

Link : https://leetcode.com/contest/weekly-contest-130/problems/binary-prefix-divisible-by-5/

2. Question

---

Given an array A of 0s and 1s, consider N_i: the i-th subarray from A[0] to A[i] interpreted as a binary number (from most-significant-bit to least-significant-bit.)

Return a list of booleans answer, where answer[i] is true if and only if N_i is divisible by 5.

매개변수로 들어온 배열이 1, 0으로 이루어져 있습니다.

이 배열들을 앞에서부터 순서대로 끊어서 2진수로 만듭니다.

ex) [0,1,1] 이 들어오면

처음에는 0,

두번째는 0,1

세번째는 0,1,1

이런식의 배열이 되는겁니다.

이런 각각의 배열 세부를 10진수로 바꾸어서 더했을때 5로 나누어 떨어지면 true를 넣고 그렇지 않으면 false를 넣은 배열을 반환하는 문제입니다.

ex) [0,1,1] 을 보면

0 -> 0

01 -> 1

011 -> 3

맨 처음 0만 5로 나누어 떨어지므로 true. 1, 3은 아니기 때문에 false를 반환합니다.

그러므로 true, false, false를 만들어 반환해야하는 그런 문제입니다.

3. Solution

---

 2진수 수들은 자리수가 늘어나면서 2씩 곱해지는것 알고계시죠?

1011 이라는 이진수가 있다고 했을때.

1 0 1 1

1*2^3 + 0*2^2 + 1*2^1 + 1*2^0 이런식으로 계산이 됩니다.

1*2^3 = 6

0*2^2 = 0

1*2^1 = 2

1*2^0 = 1

1011의 10진수 값은 9가 됩니다. 

문제에서 원한건 n자리 수를 가진 2진수를 앞에서부터 1개, 2개 3개 ... . . . .n개 짤라서 각각의 10진수값을 더했을때

5로 나누어 떨어지는 것을 구하라는 것이니까. 하나씩 계산을 하면 아래처럼 됩니다.

▼ input : [1, 1, 0, 1, 1, 1, 1]   

i=0 :           1x1 = 1   

i=1 : 1x2  +  1x1 = 3   

i=2 : 3x2  +  0x1 = 6   

i=3 : 6x2  +  1x1 = 13   

i=4 : 13x2 + 1x1 = 27   

i=5 : 27x2 + 1x1 = 55 -> true   

i=6 : 55x2 + 1x1 = 111   

위처럼 계산을 해도 되지만, 5의 배수를 판단하는것은 끝자리 수가 0, 5 인 경우만 따지면 되기 때문에,

맨 끝자리(1의자리)만 계산해도 되기때문에 아래 처럼 계산을 하면 비용을 줄일 수 있습니다.

▼ input : [1, 1, 0, 1, 1, 1, 1]   

i=0 :         1x1 = 1   

i=1 : 1x2 + 1x1 = 3   

i=2 : 3x2 + 0x1 = 6   

i=3 : 6x2 + 1x1 = 13 -> 3   

i=4 : 3x2 + 1x1 = 7   

i=5 : 7x2 + 1x1 = 15 -> 5 -> true   

i=6 : 5x2 + 1x1 = 11 -> 1  

코드로 보면 이런 공식이 나오게됩니다.

sum = sum x 2 + A[i] x 1; 

4. Source Code

---

//[C++] 1018. Binary Prefix Divisible By 5 Solution, leetcode.   
//BlockDMask.
 
class Solution {
public:
    vector<bool> prefixesDivBy5(vector<int>& A) 
    {
      vector<bool> v;
      v.reserve(A.size()); //reserve enough capacity.
 
      int sum = 0;
      for (int i = 0; i < A.size(); ++i)    //순회.
      {    
        //이전에 더한것들은 2를 곱하고, 맨끝에 추가된 자리는 1을 곱합니다.
        //2곱하기 대신에 시프트 연산을 사용해도 무방합니다.
        sum = (sum * 2) + (A[i] * 1);        
 
        if (sum > 10)
        {
          sum = sum % 10;    //1의 자리만 가지고 오기.
        }
 
        if (sum % 5 == 0)    //5로 나누어떨어지는가.
        {
          v.push_back(true);
        }
        else
        {
          v.push_back(false);
        }
      }
          return v;
    }
};

감사합니다.