[Programmers] 후보키

문제

 

2019 KAKAO BLIND RECRUITMENT > 후보키

코딩테스트 연습 - 후보키

 

 

아이디어

 

이번 문제의 아이디어는 부분집합을 이용한 완전 탐색이라고 생각합니다.

 

문제에서 요구하는 후보 키가 되기 위해서는 유일성과 최소성을 모두 만족해야 됩니다.

 

그리고 컬럼값의 최대 길이는 8까지이기 때문에 컬럼들에 대한 모든 부분집합을 구해도 시간 초과 등의 에러를 마주하지 않게 됩니다.

 

결과적으로 부분집합을 이용해 구해지는 집합 원소들을 가지고 유일성과 최소성을 모두 만족하는지를 확인하고 만족할 경우 후보 키로 등록을 해주면 문제를 풀 수 있습니다.

 

위의 생각을 기반으로 다음과 같은 알고리즘 로직을 구현할 수 있었습니다.

 

1. 부분집합을 이용하여 집합에 속하는 원소 구하기

2. 구해진 집합의 원소들이 최소성을 만족하는지 검사 (후보 키로 만족되었던 값들과 비교)

3. 집합의 원소들에 해당하는 모든 컬럼들이 모든 행에 대해 동일한 값이 있는지 검사 (유일성 검사)

4. 모두 만족할 경우 후보 키로 만족되는 리스트에 등록

5. 모든 부분집합의 원소를 탐색할 때까지 1~4를 반복

 

 

구현 코드 (Java)

 

import java.util.*;

class Solution {
    public int solution(String[][] relation) {
        int n = relation.length;
        int m = relation[0].length;
        
        List<List<Integer>> resList = new ArrayList<List<Integer>>(); // 후보키가 담긴 리스트를 담는 리스트
        
        for(int i=0; i<(1<<m); i++) { // 컬럼에 대한 부분집합 구하기
        	List<Integer> targetList = new ArrayList<Integer>();
        	for(int j=0; j<m; j++) {
        		if((i & (1<<j)) != 0) {
        			targetList.add(j);
        		}
        	}
        	
        	if(targetList.size() > 0) { // 부분집합으로 구해진 컬럼 원소가 하나라도 있을 경우
        		boolean check = true;
        		for(int a=0; a<resList.size(); a++) { // 최소성 만족 검사
        			List<Integer> saveList = resList.get(a);
        			
        			int count = 0;
        			for(int b=0; b<saveList.size(); b++) { // 부분집합으로 뽑힌 targetList와 저장된 후보키가 담긴 리스트들과 원소 비교
        				for(int c=0; c<targetList.size(); c++) {
        					if(saveList.get(b) == targetList.get(c)) {
        						count++;
        						break;
        					}
        				}
        			}
        			
        			if(count == saveList.size()) { // 후보키가 담긴 리스트의 원소들을 모두 포함하고 있을 경우
        				check = false; // 최소성 만족 실패
        				break;
        			}
        		}
        		
        		if(check) {
        			firstLoop: for(int a=0; a<n; a++) { // 유일성 만족 검사
        				for(int b=a+1; b<n; b++) {
        					int count = 0;
        					for(int c=0; c<targetList.size(); c++) { // 부분집합으로 뽑힌 컬럼 인덱스에 대해 같은 값들이 행에 있는지 확인
        						if(relation[a][targetList.get(c)].equals(relation[b][targetList.get(c)])) {
        							count++;
        						}
        					}
        					
        					if(count == targetList.size()) { // targetList의 모든 컬럼에 대해 동일한 값을 가지는 행들이 있을 경우
        						check = false; // 유일성 만족 실패
        						break firstLoop;
        					}
        				}
        			}
        		}
        		
        		if(check) { // 최소성과 유일성을 모두 만족할 경우
        			resList.add(targetList);
        		}
        	}
        }
        
        return resList.size();
    }
}

 

 

 

읽어주셔서 감사합니다.