[프로그래머스] 후보키

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42890

프로그래머스

코드

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

class Solution {
    
    List<String> candidateKey = new ArrayList<String>();
    
    public int solution(String[][] relation) {

		// 컬럼으로 가능한 모든조합을 구한다, 이미나온 후보키가 포함되는 경우는 버린다.
		int[] flag = new int[relation[0].length];
		powerSet(relation,flag,0);
        
		return candidateKey.size();
    }

    private void powerSet(String[][] relation, int[] flag, int index) {

		if( index == flag.length ) {
			String s = "";

			for ( int i = 0 ; i < flag.length; i++ ) {
				if(flag[i] == 1 ) {
					s+=String.valueOf(i);
				}
			}
			if(s.equals("") || s.equals(null)) return;
			// 후보키가 될 수 없는경우.
			if ( !candidateKey.isEmpty() ) {
				for ( int i = 0; i < candidateKey.size(); i++ ) {
					// 후보키 꺼내서 비교
					String candiKey = candidateKey.get(i);
					boolean possible = false;
					for ( char c : candiKey.toCharArray()) {
						if( !s.contains(String.valueOf(c)) ) {
							possible=true;
							break;
						}
					}
					if( !possible ) return;
				}
			}
			// 후보키가 되는지 확인한다.
			Map<String,Integer> duplicateCheck = new HashMap<String,Integer>();

			String[] arrS = s.split("");
			for ( int j = 0 ; j < relation.length; j++ ) {
				String s2 = "";
				for ( int i = 0 ; i < arrS.length; i++ ) {
					s2 += relation[j][Integer.valueOf(arrS[i])];
				}
				if ( duplicateCheck.get(s2) == null ) duplicateCheck.put(s2,1);
				else return;
			}
			// 위에서 return 되지않았다면 후보키를 추가해준다.
			candidateKey.add(s);

			return;
		}

		flag[index] = 0 ;
		powerSet(relation,flag,index+1);

		flag[index] = 1;
		powerSet(relation,flag,index+1);
	}
    
}

제출 결과

나의 풀이

처음에 문제를 이해하는데 너무 오래 걸렸다..

 

처음에 후보 키의 개념을 기본키로 구성된 집합으로 이해했었다..

 

그래서 예시에서 [ 이름, 전공 ]의 경우 이름을 제외한 [ 전공 ] 속성은 유일성이 깨지기 때문에 최소성을 만족하지 않기 때문에 불가능하다고 생각했지만.. 그게 아니라

 

[ 전공 ] 속성만으로 유일성이 깨지지 않는 것이 최소성을 만족하지 않는 것이었다 ㅠ..ㅠ

 

후보 키에 대해서 다시 숙지하고 문제를 풀이하였다.

 

먼저, 문제를 그냥 테이블 전체로 보았을 때, 칼럼의 순서는 상관이 없다.

 

그래서 기존에 { a, b, c }의 모든 부분집합을 구하는 멱집합 알고리즘을 적용해서 0~n-1개의 칼럼으로 만들 수 있는 모든 조합을 만들어가면서, 해당 칼럼에 해당하는 데이터들을 모두 비교하여 중복된 게 없다면 ( 즉, set에 추가된 데이터가 row의 개수와 동일한 경우 ) 후보 키로 추가해주었다. [ 멱집합 알고리즘 이란 ?? ]

 

주의할 점은 기존 멱집합을 구할 때는 { a, b, c }의 경우 a를 포함하는 경우, a를 포함하지 않는 경우의 순서대로 조합을 구하여 { {a, b, c}... {c} } 순서대로 조합 이구해 졌는데, 후보 키의 성격상 1개로 후보 키가 되는 경우부터 2개, 3개씩 누적해서 구해가야 하므로 조합 글자를 바꾸는 순서를 a를 포함하지 않는 경우, a를 포함하는 경우와 같이 보도록 해주었다.

 

그리고 {1,3}이나 , {1,2,3}처럼 2개 이상의 칼럼을 후보 키로 확인해야 하는 경우를 고려하여 문자열에 "13', "123"과 같이 먼저 담고, 이걸 다시 split 하여 존재하는 후보 키와 비교하도록 해주었다.

 

또 조합 칼럼으로 데이터를 비교하는 과정에서 만약 기존에 { 1,3 }이라는 후보 키가 존재했다면 이후에 { 1,2,3 }은 후보키가 될 수 없다. ( 2를 제거하였을 때 { 1,3 }이 유일성을 만족하니깐 )

 

이런 경우도 같이 고려하여, 후보 키가 되는지 확인해주었다.

 

멱집합 알고리즘을 이해하고, 그것을 응용하여 풀이한 문제였다..!