Find the size of Largest Subset with positive Bitwise AND - GeeksForGeeks

Geeks for Geeks 해외 코딩 관련 플랫폼이 있다

페이스북에서 해외 코딩 인터뷰 관련 그룹 몇개를 팔로우 하고 있는데, 그곳에는 문제와 함께 본인의 풀이를 유튜브에 올려, 문제와 풀이 영상 링크를 함께 포스팅 하는 사람들이 있다

오늘도 문제 하나가 포스팅 되었는데 제목이 무려...

 

Find the size of Largest Subset with positive Bitwise AND

 

 

엄청난 길이의 제목에 압도당해 홀린듯이 문제를 확인했고, 푸는데 꽤 애를 먹었던 문제고 내용도 괜찮아서 정리할겸 올려본다

 

아래는 문제의 링크이다

Find the size of Largest Subset with positive Bitwise AND - GeeksforGeeks

Find the size of Largest Subset with positive Bitwise AND - GeeksforGeeks

 

영어가....

 

해석해보자면,

 

길이가 N 인 배열 arr 에 대하여

arr 의 subset 들 중, 모든 원소들에 Bitwise AND 연산을 취한 결과가 1 이상인 정수 ( == 0 이 아닌 ) 인 subset 들 중 size 가 최대인 subset 의 size 를 구하시오

 

정도 되겠다

 

---

접근법

한가지 특이한 점이라면, 이 문제는 입력값의 범위가 딱히 주어지지 않았다. 하지만 그래서인지 시간복잡도에 대해서 더 고민하게 되었다.

leetCode 비슷한 해외 플랫폼 문제라 매우 독특한 최적화된 풀이가 존재하리라 생각은 했지만, 매번 그렇듯 브루트 포스부터 접근했다

 

1. 가능한 모든 Subset 을 뽑아내고
2. 각 Subset 에 대해 모든 원소들의 Bitwise AND 연산을 수행한다
   1. 각 원소들의 binary representation array 을 뽑아내고
   2. bit 들의 AND 연산을 수행
3. 연산의 결과값이 0 이 아닌 Subset 의 max size 를 업데이트

 

binary representation 부분이 조금 까다로웠는데 다음의 코드로 잘 해결했다

 

public static int[] getBinaryRepresentation(int[] bit, int number) {
	List<Integer> binaryList = new ArrayList<>();
    
    // 아래 loop 을 통해 만들어지는 bit pattern 은
    // 오른쪽이 아닌 왼쪽으로 갈수록 자릿수가 낮은 형태
    while(number > 0) {
    	binaryList.add(number % 2);
        number /= 2;
    }
    
    return binaryList.stream().mapToInt(i -> i).toArray();
}

 

 

배열 arr 의 길이가 N 이고 원소의 최대값이 K 일 때

시간복잡도는 O( 2^N * N * logK ) 이다 ( Subset 들 개수가 2^N, binary presentation 에 log K, Bitwise AND 연산들에 N )

 

2^N 부터 이건 답이 없다

DP 혹은 메모이제이션 비슷한 느낌으로 최적화가 이루어질 것 같은데

이를 위해서 Bitwise AND 연산의 특징에 조금 더 집중해 보기로 했다

 

---

풀이 - Bitwise AND 연산 결과값이 0 이 되는 조건

2 와 4 의 Bitwise AND 연산 결과를 보자

 

0 1 0		// 2
1 0 0		// 4
------	AND
0 0 0

 

둘의 AND 연산결과는 정수값으로 0 이 나온다.

 

여기에 8을 추가해보자

 

0 0 1 0		// 2
0 1 0 0		// 4
1 0 0 0		// 8
--------	AND
0 0 0 0

 

여전히 결과값이 정수로 0 이다.

이제 슬슬 뭔가 보이는 것 같기도 하다.

 

마지막으로 5를 추가해보자

 

0 0 1 0		// 2
0 1 0 0		// 4
1 0 0 0		// 8
0 1 1 0		// 5
--------	AND
0 0 0 0

 

AND 연산의 특징으로 인해 각 자릿수에 0 이 하나라도 있으면, 해당 자리의 AND 연산 결과값은 무조건 0이 된다

 

배열 arr 의 원소들이 { 2, 4, 5, 8 } 이라고 생각하고 모든 원소의 Bitwise AND 연산의 결과값이 0 이 되지 않는 하나의 Subset 을 뽑아보자

 

1 0 0		// 4
1 1 0		// 5
--------	AND
1 0 0

 

위와 같은 { 4, 5 } Subset 에서는 AND 연산의 결과값으로 0 이 아닌 정수값이 나온다

 

즉, 정수를 binary representation 으로 바꿨을 때 어느 하나 자릿수만이라도 모두 1이 된다면 해당 정수들의 Bitwise AND 연산값은 0이 아닌 정수가 되는 것이다

 

최종 연산값이 0 만 아니면 되므로, binary representation 의 자릿수에 구애받지 않는것이 포인트로,

주어진 배열 arr 의 모든 원소들의 binary representation 의 각 자릿수를 summation 했을 때 이들 중 가장 큰 값이 문제의 조건을 만족하는 Subset 의 크기가 되는 것 이다

 

문제의 예시로 주어진 { 2, 3, 7, 8, 13 } 배열의 모든 원소들의 binary representation 의 각 자릿수를 summation 해보자

 

0 0 1 0	  // 2
0 0 1 1	  // 3
0 1 1 1	  // 7
1 0 0 0	  // 8
1 1 0 1	  // 13
--------
2 2 3 2

 

이 때 최대값은 3이 되는걸 확인할 수 있다

 

고로 문제의 조건을 만족하는 Subset 의 최대크기는 3이 되는것이다.

 

이 때 시간복잡도는 O(N + logK) 로 브루트포스와 비교 시 확연하게 준것을 확인할 수 있다

 

---

응용

만약 문제의 조건을 만족하는 최대 크기의 Subset 하나를 아무거나 하나 리턴하라고 한다면 어떻게 풀 수 있을까?

 

각 자릿수를 summation 한 배열에 대해, 최대값 하나의 index 를 구하고, 해당 index 에 대해 binary representation 이 1 이 되는 정수들을 싹 모아다가 array 로 리턴하면 될 것이다