[프로그래머스] 2019 카카오 블라인드 #3 후보키 (Java)

#3 후보키

난이도 : LEVEL2

유형 : 조합, 비트마스크

코딩테스트 연습 - 후보키

▸ 문제

프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다.

그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다.

후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다.

• 관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.
  • 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
  • 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

제이지를 위해, 아래와 같은 학생들의 인적사항이 주어졌을 때, 후보 키의 최대 개수를 구하라.

 

위의 예를 설명하면, 학생의 인적사항 릴레이션에서 모든 학생은 각자 유일한 "학번"을 가지고 있다. 따라서 "학번"은 릴레이션의 후보 키가 될 수 있다.
그다음 "이름"에 대해서는 같은 이름("apeach")을 사용하는 학생이 있기 때문에, "이름"은 후보 키가 될 수 없다. 그러나, 만약 ["이름", "전공"]을 함께 사용한다면 릴레이션의 모든 튜플을 유일하게 식별 가능하므로 후보 키가 될 수 있게 된다.
물론 ["이름", "전공", "학년"]을 함께 사용해도 릴레이션의 모든 튜플을 유일하게 식별할 수 있지만, 최소성을 만족하지 못하기 때문에 후보 키가 될 수 없다.
따라서, 위의 학생 인적사항의 후보키는 "학번", ["이름", "전공"] 두 개가 된다.

릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하라.

▸ 제한사항

• relation은 2차원 문자열 배열이다.
• relation의 컬럼(column)의 길이는 1 이상 8 이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.
• relation의 로우(row)의 길이는 1 이상 20 이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.
• relation의 모든 문자열의 길이는 1 이상 8 이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.
• relation의 모든 튜플은 유일하게 식별 가능하다.(즉, 중복되는 튜플은 없다.)

 

문제 풀이  

일단 유일성, 최소성 뭔가 데이터를 구분짓기 애매한 단어들이 있어 실전이었다면 제쳐두고 풀었을 것 같다. 처음에 구상은 잘했는데 마지막에 매듭짓기에서 꽤 오래 끌었다. 모든 조합을 뽑고 중복컬럼은 예외처리해서 후보키 후보를 뽑는 것까지 설계하였지만 비트마스크로 부분집합을 예외처리해주는 부분까지 파고들 줄은 몰랐다. LEVEL 2 맞나?

 

예시로, 저장된 답 {0}, {1,2}이고 새로운 후보 {1,2,3}가 왔을 때 1,2는 이미 저장되어 있으므로 유일성으로 제거해줬는데 이 방식이 아니라 {1,2,3}의 부분집합이 현재 답에 속해있는지를 판단해야 했다. 반례로는 저장된 답 {1,2}이 있을 때 새로운 후보 {1,3}이 올 경우는 새로운 후보가 될 자질이 있으므로 저장을 해줘야 한다. 그런데 내가 설계한 방식은 해당 답을 체크해주지 못한다.

 

결론은 설계 논리 부족이었다. 그냥 조합문제라고 너무 얕보고 덤볐던 것 같다. 역시 방심은 금물이다... 그리고 뭔가 19년도 코테는 1번부터 문제자체가 쉽게쉽게 넘어가는 법이 없었다. 18년도가 너무 쉬웠어서 그런가 여기 3번부터 기분이 쎄했다. 

 

구상

1. 유일성과 최소성 개념 파악하기

문제의 핵심인 유일성과 최소성의 개념을 파악하는게 우선이었다. 글로만은 뭔가 판단하기 애매하여 예제를 보면서 규칙을 어느정도 파악했다.

 

유일성

• {이름, 학년}, {전공, 학년}의 집합은 중복 칼럼이 존재하기 때문에 후보키가 될 수 없다.

최소성

• {학번, 이름, 전공}은 {학번}만으로도 후보키가 될 수 있기 때문에 굳이 다른 튜플들과 묶일 필요가 없다.

 

2. 모든 경우의 수 구하기 (조합)

행렬 크기가 최대 8x20이라 효율성 생각안하고 무작정 설계를 해나갔다. 이제는 유일성과 최소성을 직접 비교를 해봐야하기 때문에 조합으로 모든 경우의 수를 뽑아준다. 조합의 크기는(1~row의 길이)까지 모두 뽑아줘야한다.

 

예시) row길이 4 일 때 가능한 모든 경우의 수

{1} , {2}, {3}, {4}, {1,2}, {1,3} , {1,4} , {2,3} , .... ,  {1,2,3,4}

 

3. 구해진 경우의 수로 유일성, 최소성 파악하기 (비트마스킹)

모든 조합의 경우의 수마다 유일성과 최소성을 파악해줘야 한다. 유일성은 다른 방법이 없다. 그냥 모든 원소들을 비교하면서 중복 불가능한 Map이나 Set자료구조에 넣어서 값이 중복되지 않는 경우의 수를 골라주면 된다.

 

최소성 - 이미 존재하는 후보키의 원소는 다른 후보키의 원소도 될 수 있다.

그 다음 유일성이 가능한 후보키의 후보가 최소성을 만족하는지 파악해주면 된다. 여기가 내가 헤맸던 부분이다. 단순히 이미 존재하는 후보키의 원소는 다른 후보키의 원소가 될 수 없다고 가정하면 안된다. 

 

예를 들어, 이미 후보키 {1,2}가 존재하다고 해도 유일성이 만족된다면 {1,3}도 후보키가 될 수 있다. 그러므로 이제 답을 저장해주고 부분집합을 쉽게 구할 수 있는 자료구조를 선택하여야 한다.

 

각 상태의 부분 집합과 상태를 체크하여야 하니 당연히 비트마스킹을 생각해볼 수 있다. 경우의 수를 크기가 작은 1부터 선택하여 넣어주기 때문에 뒤에 올 후보키들은 이전에 이미 등록된 후보키보다 크기가 같거나 클 수 밖에 없다. 그러므로 새로운 후보키의 부분집합을 구해줘서 최소성을 만족하는지 파악해주면 된다. 

 

이렇게 최종적으로 저장된 후보키들의 총 갯수가 답이 된다.

if(isSubKey(res)) { // 후보키가 만족되는지 (유일성)
	int cur =0;
	for(int num : res) {
		cur |= 1<<(num); // 새로운 후보키의 비트 (ex, {1,2} > 110}
	}
	if(!isSubSet(cur)) { // 부분집합에 해당되는지 (최소성)
		ans.add(cur);	// 유일성과 최소성이 만족되면 해당 상태 저장
	}
}

 

설계

1. 크기가 1~row길이가 되는 모든 경우의 수를 조합 알고리즘을 통해 구해준다. comb(int pos, int r);
2. 구해지는 row의 부분집합(경우의 수)이 후보키가 될 수 있는지 검사해준다. 부분집합: res.add(num);
   1. 유일성 체크하기 isSubKey(res)
      1. 각 칼럼을 String값을 더하여 중복되는 컬럼이 있으면 해당 집합은 후보키가 될 수 없다.
      2. 중복되는 컬럼이 없을 경우 다음 단계로 넘어간다.
   2. 최소성 체크하기 isSubSet(cur)
      1. 이미 저장된 후보키가 새로운 후보키의 부분집합인지 비트마스킹을 통해 체크해준다.
      2. !isSubSet(cur) ans.add(cur); 부분집합에 해당하지 않으면 최소성을 만족하므로 해당 부분집합을 비트의 형태로 저장해준다.

 

풀이 코드 

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;

class Solution {
	static String[][] relations;
	static Stack<Integer> s;
	static List<Integer> ans;
	static boolean[] check;
	static int row, col;
    
	public int solution(String[][] relation) {
		relations = relation;
		col = relation.length;
		row = relation[0].length;

		ans = new ArrayList<>();
		for(int i=0; i<row; i++) {
			s= new Stack<>();
			check= new boolean[row];
			comb(0, i+1);
		}
		return ans.size();
	}
	
	static void comb(int pos, int r) {
		if(s.size() == r) {
			List<Integer> res = new ArrayList<>();
			for(int num : s) {
				res.add(num);
			}
			
			if(isSubKey(res)) { // 해당 집합이 중복 컬림이 존재하는지 (유일성)
				int cur =0;
				for(int num : res) {
					cur |= 1<<(num);
				}
				if(!isSubSet(cur)) { // 부분집합에 해당되지 않는지 (최소성)
					ans.add(cur); // 후보키 만족할 경우 후보키로 저장
				}
			}
			return;
		}
		for(int i=pos; i<row; i++) {
			if(!check[i]) {
				check[i] = true;
				s.push(i);
				comb(i,r);
				s.pop();
				check[i] = false;
			}
		}
	}
	
	static boolean isSubKey(List<Integer> rowList) {
		Set<String> set = new HashSet<>();
        for(int i=0; i<col; i++) {
        	String data = "";
        	for(int row : rowList) {
        		data += relations[i][row];
        	}
        	if(set.contains(data)) {
        		return false;
    		}
    		set.add(data);
        }
        return true;
	}
	
	static boolean isSubSet(int now) {
		for(int i=0; i<ans.size(); i++) {
			int ansData = ans.get(i);
			if((ansData & now) == ansData) return true;
		}
		return false;
	}
}