[코테연습] 2275. Largest Combination With Bitwise AND Greater Than Zero

배열 / 해시테이블 / 비트 문제

문제 분석

• 목표: 주어진 배열에서 비트 AND 연산 결과가 0보다 큰 경우의 가장 큰 조합의 크기를 찾습니다.
• 조건: 각 숫자를 비트 단위로 분석하여, 동일한 비트가 1인 숫자들의 개수를 찾는 방식입니다.
• 핵심 개념: 각 비트 위치에 대해 해당 위치가 1인 숫자들의 개수를 누적하여, 가장 큰 값을 찾습니다.

문제 풀이

• 1. 비트 카운팅 배열 생성:
  • 32비트 정수를 가정하여, 각 비트 위치에서 1의 개수를 저장하기 위한 bitCount 배열을 만듭니다 (bitCount[32]).
• 2. 각 숫자에 대해 비트 레벨 분석:
  • 주어진 숫자 배열을 순회하면서 각 숫자를 비트 시프트하여 개별 비트가 1인지 확인합니다.
  • 숫자를 0번째 비트부터 31번째 비트까지 검사하며, 해당 위치의 비트가 1이면 bitCount[i]를 증가시킵니다.
• 3. 최대 비트 개수 찾기:
  • 비트 카운팅 배열을 순회하면서 각 비트 위치의 1의 개수 중 최대값을 찾습니다.
  • 이 최대값이 Bitwise AND 결과가 0보다 큰 조합의 최대 크기가 됩니다.
• 4. 결과 반환:
  • 최종적으로 찾은 최대 비트 개수를 반환합니다.

 

> java

 

class Solution {
    public int largestCombination(int[] candidates) {
        int[] bitCount = new int[32];

        // 각 숫자에 대해 비트 레벨 분석
        for (int num : candidates) {
            for (int i = 0; i < 32; i++) {
                if ((num & (1 << i)) != 0) {
                    bitCount[i] += 1;
                }
            }
        }

        // 최대 비트 개수 찾기
        int result = 0;
        for (int cnt : bitCount) {
            result = Math.max(cnt, result);
        }

        return result;
    }
}

 

> python

 

class Solution:
    def largestCombination(self, candidates: List[int]) -> int:
        bit_count = [0] * 32

        for num in candidates :
            for i in range(32) :
                if ( num & (1 << i) ) != 0 :
                    bit_count[i] += 1
        
        return max(bit_count)