본문 바로가기
algorithm

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

by onejunu 2020. 8. 30.

 

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

 

https://onejunu.tistory.com/63

 

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

아래 배열을 계속 쓸 것이다. int[] arr = new int[]{1,2,3}; # 부분 집합 구하기 코드 생각 없이 그냥 부분 집합을 구한다고 하면 어떻게 구할까?? 1 2 3 1,2 1,3 2,3 1,2,3 그렇다면 비트 마스크로 한다면 아래.

onejunu.tistory.com

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;
        }
    }

댓글