[프로그래머스] 2019 카카오 블라인드 #3 후보키 - JAVA

문제

후보키

풀이

먼저 bit를 이용하여 가능한 한 모든 어트리뷰트의 조합을 구해줍니다.

for(int i = 1; i < 1<<col; i++) {
	...
}

구한 부분집합을 통해 해당 부분집합으로 후보키가 될 수 있는지 check함수를 통해 구해줍니다.
여기서 최소성은 고려하지 않고 확인해 줬습니다. (최소성은 모든 후보키가 될 수 있는 조합을 구한 후 최소성을 만족하는 식으로 구해줄겁니다.)

구한 부분집합으로 유일성을 확보하는지 확인할려면 일단 모든 학생들에 대해서 비교를 해줘야 하므로 다음과 같이 표현해줍니다.

for(int i=0; i<row-1; i++) {
	for(int j=i+1; j<row; j++) {
    	...
    }
}

이런식으로 for문을 작성해주면 모든 학생들을 비교할 수 있습니다.
이제 구한 부분집합으로 유일성을 확인해주기 위해 다음과 같이 해줍니다.

public boolean check(String[][] relation, int subset) {
  for(int i=0; i<row-1; i++) {
      for(int j=i+1; j<row; j++) {
          boolean isSame = true;
          for(int k=0; k<col; k++) {
              if(subset & 1 << k == 0) continue;
              if(relation[i][k].equals(relation[j][k]) == false) {
                  isSame = false;
                  break;
              }
          }
          if(isSmae) return false;
      }
  }
  return true;
}

구한 부분집합(subset)이 3이라면 이진수로 0011입니다. 즉 0번째와 1번째 어트리뷰트의 조합으로 유일성을 만족하는지 확인하면 됩니다.
만약 0번째와 1번째 어트리뷰트중 하나라도 다르다는 것이 확인되면 break해줍니다.
하나의 조합만 다르다면 2개의 조합을 합쳐도 무조건 유일성이 확보되기 때문입니다.

이제 check함수를 통해 true가 return된다면 해당 부분집합을 list에 담아줍니다.

for(int i = 1; i < 1<<row; i++) {
	if(check(relation,i)) {
    	candidates.add(i);
    }
}

이제 남은것은 유일성을 만족하는 후보키들중 최소성을 만족하는 후보키의 갯수를 구해주면 됩니다.
이것은 비트연산으로 간단하게 구해줄 수 있습니다.
만약 0001과 0011이라는 2비트 값이 후보키로 있다고 합시다.
여기서 최소성을 만족할려면 0011값은 제외되어야 합니다.
이것을 and연산을 통해 구해줄 수 있습니다.
0001 & 0011을 하게되면 0001이 됩니다.
즉 (a & b == a)라면 b값은 최소성을 만족못하는 후보키가 된다는 말입니다.
코드로 나타내면 다음과 같습니다.

while(candidates.size() != 0) {
	int n = candidates.remove(0);
    answer++;
    for(Interator<Integer> it = candidates.iterator(); it.hasNext();) {
    	int c = it.next();
        if(n & c == n) {
        	it.remove();
        }
    }
}

전체코드

import java.util.*;

class Solution {
    static int row,col;
    
    public boolean check(String[][] relation, int subset) {
        for(int i=0; i<row-1; i++) {
            for(int j=i+1; j<row; j++) {
                boolean isSame = true;
                for(int k=0; k<col; k++) {
                    if((subset & (1 << k)) == 0) continue;
                    if(relation[i][k].equals(relation[j][k]) == false) {
                        isSame = false;
                        break;
                    }
                }
                if(isSame) return false;
            }
        }
        return true;
    }
    public int solution(String[][] relation) {
        int answer = 0;

        row = relation.length;
        col = relation[0].length;
        
        ArrayList<Integer> candidates = new ArrayList<>();
        
        for(int i=1; i<1<<col; i++) {
            if(check(relation,i)) {
                candidates.add(i);
            }
        }

        while(candidates.size() != 0) {
            int n = candidates.remove(0);
            answer++;
            
            for(Iterator<Integer> it = candidates.iterator(); it.hasNext();) {
                int c = it.next();c
                if((n & c) == n) {
                    it.remove();
                }
            }
        }
        
        return answer;
    }
}