[프로그래머스] 후보키 (Java)

프로그래머스 후보키

문제풀이

후보키에 대한 개념을 확실히 알고있었으면 더 쉽게 풀었을 문제다. 만약 모르고 있었다면 지문 해석을 잘 해야하는데 나는 최소성 부분에서 이해를 잘못해서 오래걸렸다.

처음에는 모든 열의 조합을 구하고 유일성 검사를 통과한 조합에 최소성 체크를 수행했다.

• 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

지문에 나와있는대로 조합에서 속성을 하나씩 빼서 유일성을 다시 체크하는 방법을 시도했는데 몇 가지 테스트케이스를 통과하지 못했다. 아마도 포함하지 못하는 경우가 있거나 call by reference의 문제 때문에 그런것 같다. 정확한 이유는 찾지못했다.(코드를 지워버려서...)

그래서 최소성의 의미를 다시 생각해보았는데 꼭 필요한 속성들로만 구성되어야 한다.에 주목했다.

• 조합의 모든 속성들은 유일성에 영향을 미쳐야한다.
• 이미 후보키로 선정된 조합이 들어있을 경우에는 어떤 속성을 추가하더라도 후보키가 될 수 있다. 그 때 추가된 속성은 유일성에 영향을 미치지않는다. 따라서 이미 후보키로 선정된 속성을 포함하는 속성조합은 최소성을 만족하지 않는다.

위 해석을 바탕으로 다시 풀이를 해보았다.

1. 모든 열(속성)의 조합을 구한다.
2. 만들어진 조합이 이전에 만들어진 후보키를 포함하는지 확인한다.
   2-1. 포함된다면 다음 조합으로 넘어간다.
   2-2. 포함되지 않는다면 유일성을 체크하여 후보키 여부를 판단한다.
3. 후보키의 갯수를 반환한다.

• Collections.containsAll은 유용하게 쓰일 것 같다.

이 문제는 데이터의 갯수가 적기 때문에 위와 같은 방법이 가능했다. 만약 데이터가 늘어난다면 비트마스크를 이용하여 문제를 풀이해야한다.

구현은 위의 순서를 똑같이 진행하면 되지만 다음과 같은 부분에서 비트마스킹을 이용한다.

• 모든 조합 구하기

  for(int set = 1 ; set < (1 << colLen) ; set++) {
  	System.out.println(Integer.toBinaryString(set));
  }

  • 1 << colLen : 1을 열의 길이만큼 왼쪽 쉬프트 연산을 하면 만들수 있는 최대 이진수의 다음 수가 나온다. ex) 1 << 4 = 10000(2)

• 포함 관계 구하기

  if((key & set) == key) return false;

  • key & set : AND 연산을 수행하면 교집합이 나온다.(둘다 1인 자리만 1) 따라서 key & set연산을 수행했을 때 set이 key를 포함한다면 key가 리턴된다.

• 자릿수 구하기

  for(int row = 0 ; row < rowLen ; ++row) {
  	for(int th = 0 ; th < colLen ; ++th) {
    		if((set & (1 << th)) != 0) {
        			...
        		}
          }
  }

  • 1 << th : th번째 자릿수를 나타낸다. ex) 1 << 3 = 1000(2)
  • set & (1 << th) : 해당 set과 같은 자리를 찾아낸다.

구현코드

import java.util.*;

class Solution {
	
	ArrayList<HashSet<Integer>> candidateKey;
	
	public int solution(String[][] relation){
		candidateKey = new ArrayList<>();
		int colSize = relation[0].length;
		
		for(int i = 1 ; i <= colSize ; ++i) {
			makeKeySet(-1, colSize - 1, 0, i, new HashSet<>(), relation);
		}
		
		return candidateKey.size();
	}

	private void makeKeySet(int attr, int maxAttr, int idx, int size, HashSet<Integer> keySet, String[][] relation) {
		if(idx == size) {
			
			for(int i : keySet) System.out.print(i + " ");
			
			for(HashSet<Integer> key : candidateKey) {
				if(keySet.containsAll(key)) {
					System.out.println("는 " + key + "를 포함합니다.");
					return;
				}
			}
			
			if(isUnique(keySet, relation)) {
				System.out.println("는 후보키 입니다.");
				candidateKey.add(keySet);
			} else {
				System.out.println("는 후보키가 아닙니다.");
			}
			
			
			return;
		}
		
		for(int i = attr + 1 ; i <= maxAttr ; ++i) {
			HashSet<Integer> newKeySet = new HashSet<>(keySet);
			newKeySet.add(i);
			makeKeySet(i, maxAttr, idx + 1, size, newKeySet, relation);
		}
	}

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

// 비트마스킹을 이용한 코드
import java.util.*;

class Solution {
	public int solution(String[][] relation) {
		ArrayList<Integer> candidateKey = new ArrayList<>();
		
		int rowLen = relation.length;
		int colLen = relation[0].length;
		
		for(int set = 1 ; set < (1 << colLen) ; set++) {
			// 최소성 검사 
			if(!isMinimal(set, candidateKey)) continue;
			
			// 유일성 검사 
			if(isUnique(set, rowLen, colLen, candidateKey, relation)) {
				System.out.println(Integer.toBinaryString(set));
				candidateKey.add(set);
			}
		}
		
		return candidateKey.size();
	}

	private boolean isUnique(int set, int rowLen, int colLen, ArrayList<Integer> candidateKey, String[][] relation) {
		HashMap<String, String> map = new HashMap<>();
		
		for(int row = 0 ; row < rowLen ; ++row) {
			String dataByKeySet = "";
			
			for(int th = 0 ; th < colLen ; ++th) {
				if((set & (1 << th)) != 0) {
					dataByKeySet += relation[row][th];
				}
			}
			
			if(map.containsKey(dataByKeySet)) return false;
			else map.put(dataByKeySet, dataByKeySet);
		}
		
		return true;
	}

	private boolean isMinimal(int set, ArrayList<Integer> candidateKey) {
		for(int key : candidateKey) {
			if((key & set) == key) return false;
		}
		
		return true;
	}
}