후보키 (Java, 비트마스크, 프로그래머스)

비트마스크를 이용하는 방법은 비트로 마스킹을 한다는 단어 자체의 의미대로 기존의 값을 이용하지 않고

비트로 바뀐 0과 1, 그리고 그 비트들의 위치만으로 값을 결정하는 방법이다.

 

비트마스크는 값, 위치 2가지 값으로 모든 경우의 수를 유니크하게 나타낼 수 있으므로 순열이나 조합을 생성할 때 사용할 수 있다.

이 문제에서도 순서가 상관없는 모든 조합을 만들어야 하기 때문에 비트마스크를 이용하여 풀이한다.

 

비트마스크를 이해하는데 핵심은 마스크가 어떠한 값을 나타내는 것이 아니라 마스크를 값에 씌워 보이는 값만 체크한다는 것이다.

{"사과", "복숭아", "바나나"}가 있을때 이 배열이 111이 되는 것이 아닌 010과 같은 비트마스크를 씌워 "복숭아"만 추출해내는 것이다.

 

비트마스크를 이용한 문제 풀이의 흐름은 다음과 같다.

 

1. 비트를 담을 List를 선언한다. 

연산을 할때 비트를 이용할 것이고 이 값이 Integer로 담기기 때문에 제네릭은 Integer로 선언.

 

2. 컬럼의 개수가 곧 경우의 수를 의미하므로 컬럼의 길이를 ( 1 << length of column )을 이용하여 비트로 펴준다.

(1 << 는 "주어진 숫자를 비트로 펴주는 동시에 + 1 해준다는 의미"이므로 비트로 펴주고 for loop를 돌리는 것만으로

해당 숫자까지 만들어낼 수 있는 모든 경우의 수를 만들어낼 수 있다.)

2-1. 유일성을 체크해야 하므로 Set 자료구조 이용. 

 

3. 2D 배열을 도는 double for loop를 선언한다.

3-1. outer for loop는 단순히 전체 배열을 순회하는 용도.

3-2. inner for loop는 배열 내의 배열을 돌며 실제 경우의 수를 만들어내는 loop이다.

3-2-1. if((i & 1 << k) > 0) 는 i의 k번째 비트가 켜져있는지를 묻는 것이다.

즉 i는 지금 만들고자 하는 조합을 뜻하는 비트를 의미하고 이게 켜져있어야지만 k를 사용할 수 있다.

k를 묻는 것이 아니라 i의 현재 상태에 대해 묻는 것이다!

 

4. inner loop를 돌고난 경우의 수를 Set에 넣는다.

4-1. outer loop까지 다 돌고나면 이제 하나의 경우의 수(i)에 대한 모든 연산을 마친 것이고 이제 유일성과 최소성을 검사해야 한다.

4-2. 유일성 검사는 모든 경우의 수를 set에 넣어두었으므로 set 값이 배열의 전체 길이(n)와 같지 않다면 유일성을 만족하지 못 했다는 의미이므로 자동으로 검사된다.

 

5. 현재의 비트(i)를 받고 정답 리스트를 돌면서 if ((i & j) == j) return false;로 부분집합 여부를 체크한다.

만약 i가 111이고 j가 011일때 i & j는 011이 될 것이고 j는 i의 부분집합이 되므로 false를 리턴한다.

011이 있다면 111이 들어와서는 안 되는 것이 최소성의 정의이다.

 

6. 모든 검사를 마치고 난 비트는 정답 리스트에 넣는다.

6-1. 모든 경우의 수를 돌고나서 정답 리스트의 길이를 반환한다.

 

import java.util.*;

class Solution{
        //비트를 담는 list.
        List<Integer> answer = new ArrayList<>();

        public int solution(String[][] relation) {
            int n = relation.length;
            int m = relation[0].length;

            //조합을 만들어내는 for loop 
            for (int i = 1; i < 1 << m; i++) {
                Set<String> set = new HashSet<>();
                //배열의 전체를 도는 for loop
                for(int j = 0; j < n; j++){
                    String temp = "";
                    //배열의 요소를 도는 for loop
                    for(int k = 0; k < m; k++){
                        if((i & 1 << k) > 0){
                            temp += (relation[j][k]);
                        }
                    }
                    set.add(temp);
                }
                //유일성을 만족하고 최소성을 만족한다면 
                if(set.size() == n && check(i)){
                    answer.add(i);
                }
            }
            return answer.size();
        }
        boolean check(int i) {
            for (int j : answer) {
                // i & j == j의 의미는 i가 j의 부분집합인지에 대한 여부를 묻는 것.
                if ((i & j) == j) return false;
            }
            return true;
        }
    }

 

레퍼런스

https://onejunu.tistory.com/64

[JAVA] 후보키 (kakao 2019 프로그래머스)