[프로그래머스] 후보키(2019 KAKAO BLIND RECRUITMENT)

 

프로그래머스에서 2019 카카오 코테에 출제되었던 후보키 문제를 풀어보았습니다.

 

 

주어진 데이터베이스에서 유일성과 최소성을 만족하는 가능한 후보키의 개수를 구하는 문제입니다.

 

이 문제에서 고려해야 할 사항은 다음과 같습니다.

 

1. 모든 키(속성)의 조합

2. 키 조합의 부분집합이 후보키에 포함되는가(최소성)

3. 키 조합으로 모든 튜플이 유니크한가(유일성)

 

여기까지 정리한 후에는 비교적 쉬운 문제라고 생각했습니다.조합 알고리즘을 이용해서 모든 키의 조합을 구하고, 최소성은 Set을 이용해야 한다는 것까지 잘 정리를 했음에도 불구하고 사용해야 하는 자료구조가 많아지다 보니 생각했던 것보다 많이 헤맸네요8ㅅ8

 

1. 모든 키(속성)의 조합

HashSet과 재귀 함수를 이용해 모든 속성들의 조합을 생성합니다.

재귀함수를 호출할 때마다 새로운 HashSet을 생성함으로써 재귀 함수에서 빠져나왔을 때 이전 상태로 돌아갈 수 있도록 합니다.(이 부분 캐치하는 데 한참 걸렸네요)

 

2. 키 조합의 부분집합이 후보키에 포함되는가(최소성)

set의 containsAll() 메소드를 이용해서 키 조합의 부분집합에 후보키가 포함되는지 확인합니다.

ex) [학번, 이름] 키 조합의 부분집합인 [학번]이 후보키에 포함될 때, [학번, 이름] 키는 최소성을 만족하지 않는다.

 

public void combinationKey(HashSet<Integer> setKey, int n, int r, int m, String[][] relation){
        if(r==0){
            for(HashSet<Integer> key: candidateKey){
                if(setKey.containsAll(key)) return; // 2. 최소성
            }
            if(isUniq(setKey, relation)){
                candidateKey.add(setKey);
            }
        }else{
            for(int i=m; i<n; i++){
                HashSet<Integer> newKeySet = new HashSet<>(setKey);
                newKeySet.add(i);
                combinationKey(newKeySet, n, r-1, i+1, relation); // 1. 모든키(속성)의 조합
            }
        }
    }

 

3. 키 조합으로 모든 튜플이 유니크한가(유일성)

HashMap을 이용해서 해당 키 조합을 통해 모든 튜플을 식별할 수 있는지 판별합니다.

public boolean isUniq(HashSet<Integer> setKey, String[][] relation){
        HashMap<String, String> hmap = new HashMap<String, String>();
        for(int i=0; i<relation.length; i++){
                String keyStr = "";
            for(int key : setKey){
                keyStr += relation[i][key];
            }
            if(hmap.containsKey(keyStr)) return false;
            hmap.put(keyStr, keyStr);
        }
        return true;
    }

 

 

전체 코드

처음 아이디어가 떠오른 것에 비해 구현하는데 어려움을 겪어서 연습이 더 많이 필요하다는 생각이 들었습니다.

상황에 맞게 여러 가지 자료구조를 활용하는 연습을 열심히!

import java.util.*;
class Solution {
    static ArrayList<HashSet<Integer>> candidateKey = new ArrayList<HashSet<Integer>>();
    static HashSet<Integer> setKey = new HashSet<Integer>();
    public int solution(String[][] relation) {
        int answer = 0;
        int attributeLen = relation[0].length;
        for(int i=1; i<=attributeLen; i++){
            combinationKey(setKey, attributeLen, i, 0, relation);
        }
        return candidateKey.size();
    }
    public void combinationKey(HashSet<Integer> setKey, int n, int r, int m, String[][] relation){
        if(r==0){
            for(HashSet<Integer> key: candidateKey){
                if(setKey.containsAll(key)) return;
            }
            if(isUniq(setKey, relation)){
                candidateKey.add(setKey);
            }
        }else{
            for(int i=m; i<n; i++){
                HashSet<Integer> newKeySet = new HashSet<>(setKey);
                newKeySet.add(i);
                combinationKey(newKeySet, n, r-1, i+1, relation);
            }
        }
    }
    public boolean isUniq(HashSet<Integer> setKey, String[][] relation){
        HashMap<String, String> hmap = new HashMap<String, String>();
        for(int i=0; i<relation.length; i++){
                String keyStr = "";
            for(int key : setKey){
                keyStr += relation[i][key];
            }
            if(hmap.containsKey(keyStr)) return false;
            hmap.put(keyStr, keyStr);
        }
        return true;
    }
}

 

+) DFS로 키 조합을 구하는 것은 속성의 수가 증가하면 불가능하므로 비트 마스크를 이용해 모든 키 조합을 구하는 방법을 사용할 수 있습니다.

import java.util.*;
class Solution {
    static ArrayList<Integer> candidate = new ArrayList<>();
    public int solution(String[][] relation) {
        int answer = 0;
        int colLen = relation[0].length;
        for(int i=0; i<(1<<colLen); i++){
            if(!checkMin(i, candidate)) continue;
            if(isUniq(i, relation)) candidate.add(i);
        }
        return candidate.size();
    }
    public boolean checkMin(int i, ArrayList<Integer> candidate){
        for(int key:candidate){
            if((i&key)==key) return false;
        }
        return true;
    }
    public boolean isUniq(int key, String[][] relation){
        HashMap<String, String> hmap = new HashMap<String, String>();
        for(int i=0; i<relation.length; i++){
            String keyStr = "";
            for(int j=0; j<relation[0].length; j++){
                if((key&(1<<j))!=0) keyStr+=relation[i][j];
            }
            if(hmap.containsKey(keyStr)) return false;
            hmap.put(keyStr,keyStr);
        }
        return true;
    }
}