프로그래머스_후보키_자바

 

 

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

코딩테스트 연습 - 후보키

 

 

후보키란 모든 튜플을 유일하게 식별할수있어야한다. => 유일성

유일성을 만족하는 후보키(혹은 후보키의 조합)들은 튜플들을 구별하는데 꼭필요한 속성들로만 이루어 져야한다 => 최소성 

 

최소성을 잘 따져줘야한다. 예를들어 (1, 3) 이 후보키라고 가정하자 그럼  1 과 3 각각은 홀로 후보키가 될수없다. 

또한 (1, 3, ~어떤 키) 와같이 1, 3 에 다른 키를 더해주면 유일성을 만족하지만 (1, 3) 만으로도 유일성을 만족시키므로 

(1, 3, ~어떤키) 조합은 최소성을 위반한다. 

 

문제풀이 

1. 일단 후보키가 될수있는 모든 조합들을 구해준다. => 구해준 후보키들의 조합을 저장해둔다.

   1-1. 이떄 유일성검사를 통과한 후보키(들) 만 저장해둔다.

2. 새로운 후보키 조합을 구할때마자 저장해둔 후보키조합이 새로운 후보키조합에 포함된다면 새로구한 후보키는 최소성을 위반함으로 추가해주지않는다.

    ex) 예를 들어 (1, 2) 가 이미 구해서 저장해둔 후보키라하자 새로구한 후보키가 (1, 2, 3) 이라한다면 (1, 2, 3)은 (1, 2)           를 포함하기 떄문에 3은 필요하지않은 키였던것이다! 그럼으로 최소성을 만족시키지 않음으로 (1, 2, 3) 조합은             후보키에 포함시켜주지않는다. 

 

새로이 알게된것 

- 다음 ArrayList (list) 를 선언시에 "( )" 안에  ArrayList(list2) 를 넣어주면 새로이 생성된 list2 는 list의 값들을 갖고있다.

	ArrayList<Integer> list = new ArrayList<Integer>();
		list.add(5);
		list.add(7);
		ArrayList<Integer> list2 = new ArrayList<Integer>(list); () 안에 list 를 넣어줬기 때문에 list2 는 list의 값을 이미 갖고 있다.
        System.out.println(list2.size()); // 2

 - list.containsAll(list2) 

ArrayList<Integer> list = new ArrayList<Integer>();
		list.add(5);
		list.add(7);
		ArrayList<Integer> list2 = new ArrayList<Integer>();
		list2.add(5);
		list2.add(7);
		list2.add(8);
		System.out.println(list2.containsAll(list));
        // list2 (5, 7, 8) 은 list (5, 7) 의 원소를 모두 포함한다. true

다음은 전체 코드이다.

// 전체 코드 
import java.util.ArrayList;
import java.util.HashSet;

class Solution {
    static ArrayList<HashSet<Integer>> candidateKey;
	static String Table[][];
	static int length;
    static int answer;
public static int solution(String[][] relation) {
        answer = 0;
        candidateKey = new ArrayList<HashSet<Integer>>();
        Table = relation;
        length = relation[0].length;
        for(int i = 1; i <= length; i++) {
        	makeSet(-1, i, 0, new HashSet<Integer>());
        }
        
        return answer;
    }
    
    public static void makeSet(int index, int target, int count, HashSet<Integer> set) {
    	
    	if(count == target) {
    		if(!isUnique(set)) {
    			return;
    		}
    		for(HashSet<Integer> key: candidateKey) { 
    			if(set.containsAll(key)) {
    				return;
    			}
    		}
    		candidateKey.add(set);    		
    		answer++;
            return;
    	}
    	
    	for(int i = index + 1; i < length; i++) {
    		HashSet<Integer> newSet = new HashSet<Integer>(set);
    		newSet.add(i);
    		makeSet(i, target, count + 1, newSet);
    	}
    	
    }
    
    public static boolean isUnique(HashSet<Integer> set) {
    	
    	ArrayList<String> list = new ArrayList<String>();
    	for(int i = 0; i < Table.length; i++) {
    		String temp = "";
    		for(int index: set) {
    			temp+= Table[i][index];
    		}
    		if(!list.contains(temp)) {
    			list.add(temp);
    		}else {
    			return false;
    		}
    	}
    	return true;
    }
}