알고리즘 99 :: 2019 카카오 블라인드 코딩테스트 - 후보키

2019 카카오 블라인드 코딩테스트 연습으로 풀어보았습니다.

 

유일성 : 한 컬럼에 대한 값이 유일하게 존재하는 것

최소성 : 유일성을 만족했음에도 다른 유일한 칼럼들을 추가해서 최소성을 깨뜨리면 안됩니다.

e.g) 나이, 학년 조합으로 최소성을 만족할 수 있는데 학번이라는 칼럼을 가지고 와서 굳이 나이, 학년, 학번 으로 후보키를 만들필요가 없다는것입니다. 

 

후보키 푸는 로직은 

후보키를 만들 수 있는 조합 -> (생성된 후보키 그룹) 포함 관계 여부 -> 유일성 검사 이후 후보키 그룹에 포함으로 해결할 수 있습니다. 

 

ㅡ. 후보키를 만들 수 있는 조합

for(int i=1; i<=relation[0].length; i++){
	make(-1, relation[0].length-1, i, 0, new HashSet<>(), relation);
}

⇢ 부분집합을 모두 생성해야 하기 때문에 위와 같은 코드를 작성합니다. 

public static void make(int a, int b, int c, int d, HashSet<Integer> keySet, String[][] relations){
	if(c==d){
    	
    }
   	for(int i=a+1; i<=b; i++){
    	HashSet<Integer> nKeySet = new HashSet<>(keySet);
        nKeySet.add(i);
    	make(i, b, c, d+1, nKeySet, realtion);
	}
}

⇢HashSet에 매번 다른 값이 들어가게 되므로 부분집합을 만들 수 있습니다. 

ㅡ. (생성된 후보키 그룹) 포함 관계 여부

for(HashSet<Integer> s : can){
	if(keySet.containsAll(s)) retrun ;
}

ㅡ. 유일성 검사 이후 후보키 그룹에 포함

if(U(keySet, relation)){
    can.add(keySet);
}


pbulic static boolean U(HashSet<Integer> keySet, String[][] relation){
	HashMap<String, String> h = new HashMap<>();
    for(int i=0; i<relation.length; i++){
    	String key ="";
        for(int c : keySet){
        	key+=relation[i][c];
        }
        if(map.containsKey(key)) return false;
        else{
			map.put(key,key);
		}
    }
    return true;
}

 

정말 잘 짠 코드를 참고하여 공부하니, 기분이 무척 좋았습니다..

 

*ref : https://www.google.com/search?q=%EC%B9%B4%EC%B9%B4%EC%98%A4+%ED%9B%84%EB%B3%B4%ED%82%A4&oq=%EC%B9%B4%EC%B9%B4%EC%98%A4+%ED%9B%84%EB%B3%B4%ED%82%A4&aqs=chrome..69i57j0l5&sourceid=chrome&ie=UTF-8