[Leetcode 2275번 문제] 2275. Largest Combination With Bitwise AND Greater Than Zero

문제 상황

The bitwise AND of an array nums is the bitwise AND of all integers in nums.

• For example, for nums = [1, 5, 3], the bitwise AND is equal to 1 & 5 & 3 = 1.
• Also, for nums = [7], the bitwise AND is 7.

You are given an array of positive integers  candidates.

Evaluate the bitwise AND of every combination of numbers of candidates. Each number in candidates may only be used once in each combination.

조합을 통해서 bitwise가 가장 긴 조합의 array 크기를 만들어라

Return the size of the largest combination of candidates with a bitwise AND greater than 0.

조합의 모든 요소의 & bitwise가 0보다 크면 된다. 한마디로 모든 요소를 and 시켰을때 그 값이 0보다 큰, 조합중 가장 긴놈의 길이를 구해라.

입력

• 1 <= candidates.length <= 10 ^ 5
• 1 <= candidates[i] <= 10 ^ 7

시간상 O(n) 또는 O(nlogn)으로 풀어야한다.

출력

위의 조건을 만족하는 가장 긴 조합의 길이, 정수

과정

단순히 생각하는게 좋은 문제다.

bitwise and 라는건 모든 수를 이진수화 했을때 특정 자리의 수가 두개 전부 1이어야 한다는걸 의미한다. 

예를들어 [16, 17, 18]의 bitwise는 16이다. 

그러면 가장 애매할 부분은 다음과 같은 예시다.

(a (b) c)와 같은 경우

a와 b가 한 개의 비트를 공유하고 b와 c가 한 개의 비트를 공유하며, 공유된 두개의 비트자리가 다를 때, 3개의 수를 모두 and하면 어떻게 될까?

a = 2(10), c = 4(100), b = 6(110)으로 치환해보면 답은 0이 나온다. 조합의 모든 수를 &해도 그 값이 0보다 크려면 모든 수가 적으도 한개의 자리에 대해 같은 비트 자리를 공유하고 있어야 한다. 

그럼 이 문제는 모든 수를 미리 비트화해서, 각 비트를 가지고 있는 수의 개수중 가장 많은 개수를 구하는 것이라고 생각할 수 있다. 그런 방식으로 문제를 풀었다.

 

알고리즘

class Solution {
    vector<int> maxes;
public:
    int largestCombination(vector<int>& candidates) {
        maxes = vector<int> (30, 0);
        for (int candidate : candidates)
        {
            int idx = 0;
            while (candidate)
            {
                if (candidate & 1)
                {
                    maxes[idx]++;
                }
                candidate >>= 1;
                idx++;
            }
        }
        int answer = 0;
        for (int candidate : maxes)
        {
            answer = max(answer, candidate);
        }
        return answer;
    }
};