카카오 코딩테스트 - 후보키

http://tech.kakao.com/2018/09/21/kakao-blind-recruitment-for2019-round-1/

2019 카카오 신입 공채 1차 코딩 테스트 문제 해설

문제는 관계형 데이터베이스에서 relation(2차원 배열)이 여기서 후보키의 개수를 찾는 문제이다.

 

후보키는 다음과 같은 두가지 성질을 만족해야 한다.

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

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

 

 



문제를 해결하는 방법은,

1. relation의 속성들(학번, 이름, 전공, 학년)에 대해 부분집합({학번},{이름},{전공},{학년},{학번,이름},{한번,이름,학년}......)을 찾는다.

2. 먼저 부분집합에서 유일성을 만족하는 집합을 찾고, 찾은 집합에 대해 최소성을 집합(내의 원소 수)을 찾는다.

 

설명을 더 하자면,

유일성을 만족하는 부분집합에는 {학번,이름},{학번,전공},{학번,학년},{학번,이름,전공}....등이 있다. 이 부분집합을 key로 하면 각 튜플을 유일하게 식별할 수 있다. 

 

하지만, 후보키가 되려면 최소성까지 만족해야 한다. 다음의 경우를 한번 보자.

 

1. {학번,이름} 

학번 속성때문에, 최소성을 만족할 수 없다. 왜냐하면 학번 자체로 튜플을 유일하게 식별할 수 있기 떄문이다. 한마디로 {이름}이 없어도 {학번} 그 자체만으로 튜플을 식별할 수 있다. 때문에 후보키가 될 수 없다.

 

2.{이름,전공}

최소성 정의에서, 구성하는 속성 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. {이름},{전공}은 각 튜플을 유일하게 식별할 수 없기 때문에 맞는 말이다. 또한, {이름,전공}서로 붙어있어야 만, 튜플을 유일하게 식별할 수 있다 때문에 후보키가 될 수 있다.

 

여기서 각 속성에 대해 부분집합을 만드는데, shift를 사용했다. 0001은 {학번}, 0010은 {이름}, 0100은 {전공}, 0111은 {학번, 이름, 전공}....이런식으로 표현하였고, 덧붙여 비트연산자를 사용하였다.

 

함수는 메인함수를 제외하고 2개를 사용하였다.

check() : 부분집합 즉, 숫자n 에서 유일성을 만족하는지

countBits() : 숫자n을 2진수로 표현했을 때 1의 위치, 즉 0100의 위치는 2

 

// https://www.welcomekakao.com/learn/courses/30/lessons/42888?language=java
// 후보키

import java.util.*;

class Solution {
    public int solution(String[][] relation) {

        int answer = 0;
        int ySize = relation.length;
        int xSize = relation[0].length;
        List<Integer> list = new LinkedList<Integer>();

        for (int i = 1; i < (1 << xSize); i++) {
            if (check(i, relation, ySize, xSize)) {
                list.add(i);
            }
        }

        Collections.sort(list, new Comparator<Integer>() {

            public int compare(Integer a, Integer b) {
                int x = countBits(a);
                int y = countBits(b);

                if (x > y) {
                    return 1;
                } else if (x < y) {
                    return -1;
                } else {
                    return 0;
                }
            }
        });

        while (list.size() != 0) {
            int n = list.remove(0);
            answer++;

            for (Iterator<Integer> it = list.iterator(); it.hasNext();) {
                int c = it.next();
                if ((n & c) == n) {
                    it.remove();
                }
            }
        }

        return answer;
    }

    boolean check(int subset, String[][] relation, int ySize, int xSize) {

        for (int y = 0; y < ySize - 1; y++) {
            for (int yy = y + 1; yy < ySize; yy++) {

                boolean isSame = true;

                for (int k = 0; k < xSize; k++) {
                    if ((subset & 1 << k) == 0) {
                        continue;
                    }
                    if (relation[y][k].equals(relation[yy][k]) == false) {
                        isSame = false;
                        break;
                    }
                }
                if (isSame) {
                    return false;
                }
            }
        }
        return true;
    }

    int countBits(int n) {

        int ret = 0;

        while (n != 0) {
            if ((n % 1) != 0) {
                ret++;
            }
            n = n >> 1;
        }
        return ret;
    }
}