[프로그래머스] 후보키 (JAVA/자바) - 2019 카카오 기출

문제

프로그래머스>코딩테스트 연습>2019 KAKAO BLIND RECRUITMENT>후보키 - https://programmers.co.kr/learn/courses/30/lessons/42890

풀이

후보키의 개념을 정확하게 이해하고 있지 않아서 헤맸던 문제이다.

일단 정리를 해보면, 후보키란 유일성과 최소성을 모두 만족하는 속성의 집합을 말한다.

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

1. 문제에도 나와있듯이, 학번 속성의 전체 값에 중복이 없기 때문에 후보키로 사용할 수 있다.

2. 하지만 이름 속성의 경우 중복된 값이 있기 때문에 튜플을 유일하게 식별할 수 없어 후보키로 사용할 수 없다.

3. 여기서 이름과 전공 속성을 묶어서 보게 되면, 두개의 값이 모두 동일한 튜플은 없기 때문에 후보키로 사용할 수 없다.

4. 이름+전공+학년을 묶어도 튜플을 유일하게 식별할 수 있지만, 이름+전공 만으로도 튜플을 유일하게 식별할 수 있기 때문에 최소성을 만족하지 못하므로 후보키가 아니다.

위 경우들을 보면 조금씩 감이 온다. 튜플을 1개 선택하는 방법, 2개 선택하는 방법, ... 해서 후보키가 가능한지 (== 값이 중복되는 게 없는지) 확인하면 된다. 속성은 0번 속성, 1번 속성, ... 과 같이 번호로 표시한다.

예를 들어, 1번 속성에 대한 값이 중복이 없다면 1번 속성은 후보키로 사용할 수 있다는 것을 알아낸 것이다.

또한 2+3+4번 속성을 후보키로 사용이 가능한지 보려고 했는데, 이미 3번 속성 혹은 2+4번 속성과 같은 집합들이 후보키로 사용이 가능하다는 것으로 알아냈다면 2+3+4는 최소성을 만족시키지 못해 후보키가 될 수 없다.

이러한 개념을 코드에 적용해서 풀이하면 된다!

코드

import java.util.HashSet;

public class Solution {
    
    static String[][] g_relation;	// global variable
    static HashSet<String> set; 	// 후보키가 가능한 튜플의 집합을 저장

    public static int solution(String[][] relation) {
        g_relation = relation;

        set = new HashSet<>();

        // 튜플을 1개 선택하는 방법, 2개 선택하는 방법, ...
        for (int i = 1; i <= relation[0].length; i++) {
            boolean[] selected = new boolean[relation[0].length];
            dfs(0, 0, i, selected);
        }
        
        return set.size(); // 가능한 후보키의 개수 리턴
    }

    public static void dfs(int idx, int cnt, int max, boolean[] selected){
        if(cnt==max){
            
            // 선택된 colume들을 string으로 만듬
            // 2번째, 4번째 colume들이 선택되었다면 cols="24"
            String cols = "";
            for (int i = 0; i < selected.length; i++) {
                if(selected[i]){
                    cols += i;
                }
            }
            
            // 선택된 colume들의 집합이 후보키로 사용 가능한지 확인
            if(findIsPossible(cols, selected)){ 
                set.add(cols);
            }
            return;
        }

        if(idx>=selected.length) return;

        selected[idx] = true;
        dfs(idx + 1, cnt + 1, max, selected);

        selected[idx] = false;
        dfs(idx + 1, cnt, max, selected);
    }

    public static boolean findIsPossible(String cols, boolean[] selected) {

        // 최소성이 만족되는지 확인
        // cols 안에 set에 들어있는 `후보키가 가능한 colume들의 집합의 요소들`이 모두 포함되어있는지 확인
        for (String s : set) {
            boolean flag = true; 
            for (int i = 0; i < s.length(); i++) {
                if(!cols.contains(s.charAt(i)+"")){
                    flag = false;
                }
            }

            if(flag){ // 모두 포함되어있으면
                return false;
            }
        }

        // 몇번 colume들을 확인해야하는지 처리
        // 예를 들어, cols가 24라면 (== 2, 4번 colume 집합이 후보키가 되는지 확인해야 한다면)
        // col_name[] = {2,4} 가 된다.
        HashSet<String> values = new HashSet<>();
        int[] col_name = new int[cols.length()];
        int idx = 0;
        for (int i = 0; i < selected.length; i++) {
            if(selected[i]){
                col_name[idx++] = i;
            }
        }

        // 값의 중복이 있는지 확인. 중복된 값이 있다면 후보키로 사용될 수 없음
        String value = "";
        for (int i = 0; i < g_relation.length; i++) {
            value = "";
            for (int j = 0; j < col_name.length; j++) {
                value += g_relation[i][col_name[j]];
            }
            if(values.contains(value)){
                return false; // 중복이 없다면 false 리턴
            }else{
                values.add(value);
            }
        }

        return true;
    }
}

정리

난이도 : LEVEL 2

🤦‍♀️ 메모

• 같은 level2 문제인데 난이도 차이 무엇 ,,, 최소성을 만족해야한다 라는 후보키의 개념을 이제서야 제대로 이해했다 ㅎ

• 그리고 234안에 2,4가 포함되어 있는지를 확인 해야하는 것이기 때문에 str.contains(24)를 쓰면 안된다! 문자열에서 특정 문자가 포함되어있는지 확인하면 된다고 잘못 생각해서 틀렸었음. 각각(2,4 둘다) 들어있는지 확인해주어야 함.

참고 사이트

딱히 없음