[PG] 42890. 후보키

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

여담

코딩테스트를 풀어보면서 요즘 느낀 것이 있다..

문자열 처리하는 것이 대체로 많이 나오는 것 같다. ( 해쉬 등등.. )

프로그래머스 문제들도 보면 해쉬문제나 문자열 처리 문제가 많으므로 많이 풀어보고 있는 중이다.

접근 방법

먼저 문제의 지문을 잘 파악해야 된다. ( 후보키의 정의 )

유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.

최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

1. 먼저 속성 값에 대해서 집합을 조합으로 뽑아냈다.

// 조합으로 뽑아 낼 r에 대한 것을 넣어쥼
for(int i=1; i<=colSize; i++){
            permutation(0,i, new boolean[colSize]);
}
static void permutation(int start, int r, boolean[] is){
            ... 생략
}

2. 이제 유일성을 체크해 준다.

HashSet<String> hashSets = new HashSet<>();
            for(int i=0; i<map.length; i++){
                StringBuilder sb = new StringBuilder();
                for(int k=0; k<check.size(); k++){
                    sb.append(map[i][check.get(k)]);
                }
                if(!hashSets.add(sb.toString())){
                    return;
                }
            }

3. 유일성을 만족했다면 최소성도 만족해야 한다.

   • 최소성은 만약 1번째 속성이 후보키라면 { 1, 2 } 의 속성은 후보키가 되지 못한다.

     Ex ) { 2 , 3 } ⇒ { 3, 2 } 똑같은 후보키 && { 2, 3 }가 후보키라면 ⇒ { 2, 4, 3 }는 최소성 만족 X

StringBuilder tempAnswer = new StringBuilder();
            for(int i=0; i<check.size(); i++){
                tempAnswer.append(check.get(i));
            }
            for(int i=0; i<answer.size(); i++){
                int answerCnt = answer.get(i).length();
                for(int k=0; k<tempAnswer.length(); k++){
                    if(answer.get(i).indexOf(tempAnswer.charAt(k)) != -1){
                        answerCnt --;
                    }
                }
                if(answerCnt == 0) return;
            }

Need Know

1. 해쉬..?

전체 코드 ( Java )

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;

class Solution {
    static String[][] map;
    static int colSize;
    static ArrayList<String> answer = new ArrayList<>();

    public int solution(String[][] relation) {
        map = relation;
        colSize = relation[0].length;

        for(int i=1; i<=colSize; i++){
            permutation(0,i, new boolean[colSize]);
        }

        return answer.size();
    }
    static void permutation(int start, int r, boolean[] is){
        if(r == 0){
            ArrayList<Integer> check = new ArrayList<>();
            for(int i=0; i<is.length; i++){
                if(is[i]){
                    check.add(i);
                }
            }
            HashSet<String> hashSets = new HashSet<>();
            for(int i=0; i<map.length; i++){
                StringBuilder sb = new StringBuilder();
                for(int k=0; k<check.size(); k++){
                    sb.append(map[i][check.get(k)]);
                }
                if(!hashSets.add(sb.toString())){
                    return;
                }
            }
            StringBuilder tempAnswer = new StringBuilder();
            for(int i=0; i<check.size(); i++){
                tempAnswer.append(check.get(i));
            }
            for(int i=0; i<answer.size(); i++){
                int answerCnt = answer.get(i).length();
                for(int k=0; k<tempAnswer.length(); k++){
                    if(answer.get(i).indexOf(tempAnswer.charAt(k)) != -1){
                        answerCnt --;
                    }
                }
                if(answerCnt == 0) return;
            }
            answer.add(tempAnswer.toString());
            return;
        }
        for(int i = start; i<colSize; i++){
            is[i] = true;
            permutation(i+1, r-1, is);
            is[i] = false;
        }
    }
}