[프로그래머스] 후보키 / 2019 KAKAO BLIND RECRUITMENT - JAVA

🖇️ 문제 링크

코딩테스트 연습 - 후보키

프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다. 그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다. 후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다.

https://programmers.co.kr/learn/courses/30/lessons/42890

 

---

📝 문제 분석

각 컬럼들의 모든 부분 집합을 만든다.

이 부분집합에 해당하는 속성들을 뽑아서 set에 저장

set사이즈와 튜플 사이즈가 같다면 후보키

이제 최소성 만족해야함

후보키 등록할 때, 기존 후보키가 지금 내가 만든 후보키에 포함되면 x → &연산으로 확인

 

 

---

⌨️ 코드

import java.util.*;

class Solution {
    public int solution(String[][] relation) {
        // 튜플 개수
        int n = relation.length;
        // 속성 개수
        int m = relation[0].length;
        ArrayList<Integer> ans = new ArrayList<>();
        // 부분 집합 생성
        for(int i = 1; i < (1 << m); i++) {
            HashSet<String> s = new HashSet<>();
            for (String[] strings : relation) {
                String now = "";
                for (int k = 0; k < m; k++)
                    if ((i & (1 << k)) != 0)
                        now += strings[k];
                s.add(now);
            }
            
            if(s.size() == n && chk(ans, i))
                ans.add(i);
        }
        
        return ans.size();
    }

    static boolean chk(ArrayList<Integer> al, int now) {
        for (Integer n : al)
            if ((now & n) == n)
                return false;
        return true;
    }
}

 

 

 

 

Uploaded by Notion2Tistory v1.1.0