Set의 사이즈가 전체 튜플의 수와 같다면 튜플을 유일하게 식별할 수 있다는 의미이므로 후보키가 되는 컬럼 조합이다.
컬럼이 4개라 하면 0, 1, 2, 3, 01, 02, 03, 12, 13, 23, 012, 013, 023, 123, 0123처럼 컬럼 갯수가 다른 조합까지 어떻게 식으로 표현해야 하나?
위 고민을 해결해주는 개념이 있다. 바로 비트마스크다.
비트마스크로 집합을 구현하는 방식을 이용하면 손쉽게(?) 해결할 수 있다.
열의 갯수를 colNum이라 하면 0 < k < (1<<colNum)까지의 이진수(컬럼 조합)중에서 유일성과 최소성을 만족하는 k의 갯수를 구한다.
주어진 숫자가 최소성을 만족하는지 확인하는 메소드
기존 키가 0011이고 현재 키가 1011이라면 0011 & 1011 = 0011 즉, 기존 키와 값이 같다.
List<Integer> keys = new ArrayList<>();
boolean checkIfMin(int i) {
for (Integer key : keys) {
if ((key & i)==key) return false;
}//for end
return true;
}
현재 키의 최소성 체크를 먼저 한다.
유일성은 위에서처럼, k 이진수에서 값이 1인 자릿수의 문자열을 붙인 뒤 Set에 넣어 전체 튜플 수와 비교한다.
public static int solution(String[][] relation) {
int rowNum = relation.length; //행수
int colNum = relation[0].length; //열수
//한 키당 해당 컬럼의 튜플 값 저장할 set
Set<String> set = new HashSet<>();
//키에서 값이 1인 자릿수의 문자열 붙일 sb
StringBuilder sb = new StringBuilder();
for (int k = 0; k < (1<<colNum); k++) {
//현재 키 최소성 체크
if(!checkIfMin(k)) continue;
//set 초기화
set.clear();
for (int i = 0; i < rowNum; i++) {
//sb 초기화
sb.setLength(0);
for (int j = 0; j < colNum; j++) {
if (((1<<j) & k) > 0) {
//현재 키에서 값이 1인 자릿수에 해당하는 j 인덱스에
//해당하는 문자열을 sb에 붙인다.
sb.append(relation[i][j]);
}
}//for end
//조립한 문자열을 set에 넣었을 때 false라면
//유일성이 만족하지 않은 것이므로 해당 key에 대해 break
if (!set.add(sb.toString())) break;
}//for end
//해당 키에서의 set 사이즈가 튜플의 수와 같다면
//유일성 만족하므로 후보키 저장 리스트에 추가
if(set.size()==rowNum) keys.add(k);
}//for end
return keys.size();
}//solution() end
참고