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

 

여기서 사용한 모든 기술은 아래 글에 기록하였다.

 

https://onejunu.tistory.com/63

[JAVA] 비트 연산자를 이용하여 조합 & 부분집합 & 부분집합 여부파악

import java.util.*;
class Solution{

        static List<Integer> ans = new ArrayList<>();

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

            for(int i=1;i<1<<m;i++){
                Set<String> set = new HashSet<>();
                for(int j=0;j<n;j++){
                    String now = "";
                    for(int k=0;k<m;k++){
                        if((i & 1<<k) > 0 ){
                            now += (relation[j][k]);
                        }
                    }
                    set.add(now);
                }
                if(set.size()==n && isPossible(i)){
                    ans.add(i);
                }
            }
            return ans.size();
        }

        private boolean isPossible(int i) {
            Iterator<Integer> iterator = ans.iterator();
            while(iterator.hasNext()){
                int next = iterator.next();
                if((next & i) == next) return false;
            }
            return true;
        }
    }