코딩테스트 문제 (18) - 후보키

카카오 2019 블라인드 코딩테스트 문제입니다. 데이터베이스의 후보키의 수를 추출하는 문제입니다.

문제

1. relations = [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],
                ["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]]
=> 2 ([0], [1,2])

풀이

먼저 유일성을 확인하기 위해 칼럼의 모든 부분 집합을 생성해야 합니다. 부분 집합을 만드는 것은 dfs로 구현할 수 있고 만든 부분 집합이 유일성을 만족하는 지 확인합니다. 그 후, 유일성을 만족하는 부분 집합에 대해 최소성 검증을 하여 최소성을 만족하는 부분 집합만 추출하면 되는 문제입니다.

kaggle.com의 notebook으로 작성한 풀이는 다음과 같습니다.

홍머스 정리

• 난이도: 중, 모든 부분 집합을 빠르게 구하는 것이 관건
• dfs 말고 bit 연산으로도 해결할 수 있다.