[プログラマLv.2-候補キー]

##問題分析
質問のタイプ
問題のタイプは,あるアルゴリズムを知ってこそ解決できる問題というより,総合的な実施能力が必要な問題であると考えられる.

インプリメンテーション

実装は大きく4つの点に分けることができる.
Point 1-可能なすべての候補キーの組み合わせを作成
Point 1-col数による可能な組合せ数
Ex)
col:1------->2^1==1<<1==10(バイナリ)(1-1)
col:2------>2^2==1<2==100(バイナリ)(1-11)
col:3------>2^3==1<3=1000(バイナリ)(1-111)

int col = relation[0].length; // col의 갯수
int possibleCnt = 1 << col;       
for(int i = 1 ; i < possibleCnt ; i++) int keySet = i;

Point 2-可能なすべての候補キーの組み合わせから一意性を満たす候補キーのみを抽出
Point 2−選択したCoolが一意性を満たすかどうかを決定する.

セットおよび

Bit演算子で1の位置を見つける能力があるはずです.

    /*
    	Point2 - 선택한 Col들이 Uniqueness를 만족하는지 판단.
     */
    boolean isUnique(int keySet, String[][] relation){
        int col = relation[0].length;
        List<Integer> list = new ArrayList<>();
        Set<String> set = new HashSet<>();
        // keySet중에서 1의 index를 찾는 과정.
        // 만약, 0110이면 list에는 [1,2]가 담긴다. -> 가장 오른쪽이 index 0이다.
        for(int i  = 0 ; i < col; i++){
            if(((keySet >> i) & 1) == 1) list.add(i);
        }
        // tuple중에서 list에 있는 index만을 이용해서 하나의 String을 만들고
        // 해당 String을 이용해서 중복을 검사한다.
        for (String[] tuple : relation) {
            StringBuilder str = new StringBuilder("");
            for (Integer idx : list) {
                str.append(tuple[idx]);
            }
            if(!set.add(str.toString())) return false;
            // 새로 만든 문자열이 set에 들어가지 않으면 이미 똑같은게 있다는 의미이기 때문에 early return 한다.
        }
        return true;
    }

Point 3-ソート候補キーの組み合わせ
Point 3-私は自分の必要に応じて選択した内容をソートすることができますか?
この問題では,バイナリで表す場合,整数値を1の個数の少ない順にソートする能力が必要である.
つまり、Comparatorは好きなように使えるようにしなければなりません.

        // 해당 keySet들을 1의 갯수를 적게 가진 순으로 정렬한다.
        Collections.sort(uniquenessOks, new Comparator<Integer>() {

            int getCntOf1(int n){
                int cnt = 0;
                while (n != 0){
                    if((n & 1) == 1)  cnt++;
                    n = n >> 1;
                }
                return cnt;
            }

            @Override
            public int compare(Integer o1, Integer o2) {
                 int cnt1 = getCntOf1(o1);
                 int cnt2 =  getCntOf1(o2);
                 return Integer.compare(cnt1, cnt2);
            }
        });

        return uniquenessOks;
    }

Point 4-一意性を満たす候補鍵から最小性を満たす候補鍵を抽出する
巡回中に値の変動が生じるため、奇形器を使用することが望ましい.
for loopをindexとして巡回する方法は適切ではありません.巡回中にindexが変わるからです.

   public List<Integer> findMinimality(List<Integer> uniquenessOk){
        List<Integer> minimalityOk = new ArrayList<>();

        while(!uniquenessOk.isEmpty()){
            int cur = uniquenessOk.remove(0);
            minimalityOk.add(cur);
            Iterator<Integer> iterator = uniquenessOk.iterator();

            while (iterator.hasNext()){
                if((iterator.next() & cur) == cur) iterator.remove();
            }
        }

        return minimalityOk;
    }

さまよう部分

ハーマンセクションの整理
誤ったアクセス方法:最初は逆トレースで問題にアクセスします.
DFSを使用して、すべての可能な組合せを作成します.この組合せが一意性を満たす場合
この組み合わせに新しいものを追加するすべての状況を排除するために,分岐を行った.
しかし、私は間違った問題を理解しました.
(0、1、2、3)4つの列がある場合:
(1,2)一意性を満たすと言えば分岐する.
(1,2,3)
(1,2,3,4)
(1,2,4)自動排除.
しかし,その後(2)が一意性を満たすと,(1,2)が最小性を満たすことができず,候補鍵として用いることができない.つまり,当初の問題処理方式は誤りであった.
正しい方法:

一意性を満たすすべての部分セットを見つけます.

要素サイズの昇順配列部でダイバーシティします.

小さな部分集合から確認を開始し、その部分集合を部分集合とする大きな部分集合を削除します.

取得する

部分集合の表現
DFSの方法ですべての部分集合を求めることができるが,これは複雑すぎる.
このとき,バイナリの特性を利用して,部分集合を表現できる方法はこの問題から分かる.
この表現を用いると,AはBが部分集合の一部集合であり,ビットマスクによりこの問題を容易に解決できることも分かった.
{"A"、"B"、"C"、"D"}のサブセットの1つ:
リストとして{'C'、'D'}を表す場合は、2つのfor loopを使用して、そのセットが{'C'、'D'および'E'のセットの一部のセットであることを決定する必要があります.
でも、
A:{'C','D'}は3-->(バイナリ=001);
B:{'C'、'D'、'E'}は7->(バイナリ=0111)である.
もしそうなら、AがBのサブセットだと判断するために、
A==B&Aであることを確認すれば良いので、定数時間で終了します.
あとで部分集合を表現するときは、このように部分集合をビットで表現することも考えたほうがいいです.

フルコード[マイコード]

package programmers.level2.후보키;

import java.util.*;

public class Solution {

    public static void main(String[] args) {
        String[][] relation = {
                {"100","ryan","music","2"},
                {"200","apeach","math","2"},
                {"300","tube","computer","3"},
                {"400","con","computer","4"},
                {"500","muzi","music","3"},
                {"600","apeach","music","2"}
        };
        Solution solution = new Solution();
        System.out.println(solution.solution(relation));
    }

    public int solution(String[][] relation) {
        int answer = 0;
        List<Integer> uniqueKeySet = findUniqueness(relation);
        List<Integer> answerList = findMinimality(uniqueKeySet);
        return answerList.size();

    }

    /*
    Point4 - Iterator를 이용하여 최소성을 만족하지 않는 key들 제거하기
     */
   public List<Integer> findMinimality(List<Integer> uniquenessOk){
        List<Integer> minimalityOk = new ArrayList<>();

        while(!uniquenessOk.isEmpty()){
            int cur = uniquenessOk.remove(0);
            minimalityOk.add(cur);
            Iterator<Integer> iterator = uniquenessOk.iterator();

            while (iterator.hasNext()){
                if((iterator.next() & cur) == cur) iterator.remove();
            }
        }

        return minimalityOk;
    }

    /*
    Point2 - 선택한 Col들이 Uniqueness를 만족하는지 판단.
     */
    boolean isUnique(int keySet, String[][] relation){
        int col = relation[0].length;

        List<Integer> list = new ArrayList<>();
        Set<String> set = new HashSet<>();

        for(int i  = 0 ; i < col; i++){
            if(((keySet >> i) & 1) == 1) list.add(i);
        }

        for (String[] tuple : relation) {
            StringBuilder str = new StringBuilder("");
            for (Integer idx : list) {
                str.append(tuple[idx]);
            }
            if(!set.add(str.toString())) return false;
        }

        return true;
    }

    List<Integer> findUniqueness(String[][] relation){
        ArrayList<Integer> uniquenessOks = new ArrayList<>();
        int col = relation[0].length; // col의 갯수
        int possibleCnt = 1 << col;

        /*
        Point 1 - col 갯수에 따른 가능한 조합의 갯수
        각각의 col을 key의 attribute로 포함할지, 포함하지 않을지를 고려 해야 하기 때문에

        Ex)
            col : 0 ------> 2^0 == 1 << 0 == 1(2진수)
            col : 1 ------> 2^1 == 1 << 1 == 10(2진수)
            col : 2 ------> 2^2 == 1 << 2 == 100(2진수)
            col : 3 ------> 2^3 == 1 << 3 == 1000(2진수)
         */
        for(int i = 1 ; i < possibleCnt ; i++){
            int keySet = i;
            if(isUnique(keySet, relation)) {
                uniquenessOks.add(keySet);
            }
        } // 유일성을 만족하는 것들을 찾아내고

        /*
        Point3 - 선택한 것들을 내가 원하는 기준으로 정렬 할 수 있는가?
        이 문제에서는 2진수로 표현했을때 1의 갯수가 적은 순으로 integer 값을 정렬 할 수 있는 능력이 필요하다.
        즉, Comparator를 평소에 원하는 입맛대로 사용 할 수 있는 능력이 있어야 한다.
         */
        // 해당 keySet들을 1의 갯수를 적게 가진 순으로 정렬한다.
        Collections.sort(uniquenessOks, new Comparator<Integer>() {

            int getCntOf1(int n){
                int cnt = 0;
                while (n != 0){
                    if((n & 1) == 1)  cnt++;
                    n = n >> 1;
                }
                return cnt;
            }

            @Override
            public int compare(Integer o1, Integer o2) {
                 int cnt1 = getCntOf1(o1);
                 int cnt2 =  getCntOf1(o2);
                 return Integer.compare(cnt1, cnt2);
            }
        });

        return uniquenessOks;
    }
}

に感銘を与える

アルゴリズム技術の育成も重要だが、最終的に最も重要なのは問題を正しく理解することであるようだ.

リファレンス

ezswのYouTube動画

関連リンクに向かい、親切で直感的に説明します.

関連のビデオを見ると、問題を正確に理解することができます.