[JAVA 문제 풀이] 406. 후보키

내가 작성한 코드

import java.util.*;

class Solution {
    List<Integer> candidateKeys = new ArrayList<>(); // 후보키들의 조합(비트마스크 형태)을 저장하는 리스트

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

        // 모든 컬럼 조합을 비트마스크로 순회 (1 ~ (1<<colLen)-1)
        for (int bitmask = 1; bitmask < (1 << colLen); bitmask++) {
            // 유일성을 만족하는지 확인
            if (!isUnique(relation, bitmask)) continue;

            // 최소성을 만족하는지 확인
            if (!isMinimal(bitmask)) continue;

            // 두 조건 모두 만족하면 후보키로 인정
            candidateKeys.add(bitmask);
        }

        return candidateKeys.size(); // 후보키 개수 반환
    }

    // 유일성 검사 메서드 >> 해당 비트마스크로 선택된 컬럼들의 조합이 유일한지 확인
    private boolean isUnique(String[][] relation, int bitmask) {
        Set<String> seen = new HashSet<>(); // 유일한 조합들을 집합에 저장

        for (String[] tuple : relation) {
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < tuple.length; i++) {
                if ((bitmask & (1 << i)) != 0) {
                    sb.append(tuple[i]).append("|"); // 구분자 붙여서 문자열 결합
                }
            }

            // 이미 본 조합이면 유일성 실패
            if (!seen.add(sb.toString())) {
                return false;
            }
        }

        return true;
    }

    // 최소성 검사 메서드 >> 이미 존재하는 후보키가 포함되어 있으면 최소성 위배
    private boolean isMinimal(int bitmask) {
        for (int key : candidateKeys) {
            if ((key & bitmask) == key) {
                return false;
            }
        }

        return true;
    }

}

다른 사람의 코드

import java.util.*;

class Solution {
    public int solution(String[][] relation) {
        int n = relation.length; // n개의 데이터
        int m = relation[0].length; // m개의 컬럼
        ArrayList<Integer> list = new ArrayList<Integer>();

        // 완전 탐색을 돈다.
        for (int i = 1; i < (1 << m); i++) {
            Set<String> s = new HashSet<String>();
            // n개의 데이터
            for (int j = 0; j < n; j++) {
                String now = "";
                // m개의 컬럼
                for (int k = 0; k < m; k++) {
                    // 모든 경우의 수 & 해당 라인 데이터 조합.
                    if ((i & (1 << k)) > 0) {
                        now += relation[j][k];
                    }
                }
                s.add(now);
            }
            if (s.size() == n && possi(list, i))
                list.add(i);
        }
        // System.out.println(list.size());
        return list.size();
    }

    // 최소성을 만족하는지 확인하는 메서드
    public static boolean possi(ArrayList<Integer> list, int now) {
        for (int i = 0; i < list.size(); i++) {
            // 같으면 최소성을 만족하지 못함.
            if ((list.get(i) & now) == list.get(i)) {
                return false;
            }
        }
        return true;
    }
}

• 비트마스킹
• 비트마스킹은 정수의 비트를 이용해 어떤 항목의 포함 여부를 나타내는 방식

컬럼 인덱스	컬럼명	비트 위치 (1 << i)
0	학번	1 (0001)
1	이름	2 (0010)
2	전공	4 (0100)
3	학년	8 (1000)