[알고리즘 TIL] 후보키

문제

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

프로그래머스

프로그래머스 LV2

설명

유일성과 최소성을 만족시키는 후보키를 찾는 문제이다.

나는 시나리오를 다음과 같이 짰다.

1. 1부터 컬럼 수만큼 반복을 돌면서 만들 수 있는 모든 조합을 생성한다.
2. 이때, 이미 후보키로 확정된 컬럼이 있으면 제외하고 조합을 생성한다.
3. 생성된 모든 조합을 가지고 유일성을 만족하는지 확인한다. 

 

여기서 2번에 대한 코드 구현에 대한 고민이 있었다. 조합을 구현할 줄은 아는데, 특정한 인덱스들을 제외하는 방법을 고안해내지 못했기 때문이다. 구글에 찾아본 결과, 다음과 같이 validColumns 배열을 따로 생성해서 해당 인덱스들을 가지고 조합을 만들면 됐다.

//exceptionColumnIndexs를 제외한 validColumnIndexs를 구해서,
//validColumnIndexs의 인덱스를 기준으로 조합을 구하면 됨! ([0,2,3] -> [valid[0],valid[2],valid[3]]
List<Integer> validIndexes = new ArrayList<>();
for (int i = 0; i < n; i++) {
	if (!exceptColumnIndexs.contains(i)) {
		validIndexes.add(i);
	}
}
if (validIndexes.size() < r) return combinations;

int[] comb = new int[r];
for (int i = 0; i < r; i++) {
	comb[i] = i;
}

//하던대로 조합 구현

 

그래도 정답이 아니였다. 생각해보니, 후보키의 모든 인덱스를 exceptColumnIndexs에 넣으면 안되고, 만들어진 조합이 후보키 부분집합을 가지고 있는지를 체크해야한다!

원래 코드에서 마지막에 부분집합 여부만 확인하면 된다.

private Set<Integer> toSet(int[] comb) {
            Set<Integer> set = new HashSet<>();
            for (int i : comb) set.add(i);
            return set;
        }

private boolean isMinimal(int[] comb) {
            Set<Integer> keySet = toSet(comb);
            for (Set<Integer> candidate : candidateKeys) {
                if (keySet.containsAll(candidate)) return false; 
            }
            return true;
        }

구현

import java.util.*;

class Solution {
    static List<Set<Integer>> candidateKeys = new ArrayList<>();
    
    public int solution(String[][] relation) {
            int answer = 0;

            //1부터 속성의 갯수까지 반복문 돌리기
            for (int i = 1; i <= relation[0].length; i++){
                //묶을 갯수를 전달하여 만들 수 있는 조합 생성하기
                List<int[]> combinations = make_combinations(i,relation[0].length);
                System.out.println();
                //조합에서 실제로 유일성을 만족하는지 확인하기
                for(int[] combination : combinations) {
                    int flag = 1;
                    List<List<String>> datas = new ArrayList<>();
                    //주어진 튜플들에서 조합에 속한 인덱스들을 뽑아 유일성 판단
                    for(int j = 0 ; j< relation.length; j++) {
                        List<String> data = new ArrayList<>();
                        for(int combinationIndex : combination) {
                            data.add(relation[j][combinationIndex]);
                        }
                        if(datas.contains(data)) {
                            flag = 0;
                            break;
                        }
                        datas.add(data);
                    }
                    if (flag==1) {
                        //최소성 판단
                        if (!isMinimal(combination)) continue;
                        candidateKeys.add(toSet(combination));
                        answer++;
                    }
                }
            }

            return answer;
        }

        private Set<Integer> toSet(int[] comb) {
            Set<Integer> set = new HashSet<>();
            for (int i : comb) set.add(i);
            return set;
        }

        private boolean isMinimal(int[] comb) {
            Set<Integer> keySet = toSet(comb);
            for (Set<Integer> candidate : candidateKeys) {
                if (keySet.containsAll(candidate)) return false;
            }
            return true;
        }

        private List<int[]> make_combinations(int r, int n) {
            List<int[]> result = new ArrayList<>();
            int[] comb = new int[r];
            for (int i = 0; i < r; i++) comb[i] = i;

            while (true) {
                result.add(comb.clone());

                int i = r - 1;
                while (i >= 0 && comb[i] == n - r + i) i--;
                if (i < 0) break;

                comb[i]++;
                for (int j = i + 1; j < r; j++) {
                    comb[j] = comb[j - 1] + 1;
                }
            }

            return result;
        }
    
}