[프로그래머스] 42890. 후보키

문제 링크

[프로그래머스] 42890. 후보키

풀이 과정

릴레이션의 모든 튜플에 대해 후보키의 개수를 구하는 문제입니다.

예를 들어, 아래와 같은 릴레이션은 밑의 사진과 같이 각 속성을 2진수 비트로 표현할 수 있습니다.

따라서, 위와 같이 네 개의 속성이 존재하면, 비트 표현으로 15가지의 슈퍼키 를 나타낼 수 있습니다.

for (int i = 1; i < (1 << n); i++) { // ①
    Set<String> set = new HashSet<>();

    for (int j = 0; j < m; j++) {
        StringBuilder sb = new StringBuilder();

        for (int k = 0; k < n; k++) {
            if ((i & (1 << k)) != 0) sb.append(relation[j][k]); // ②
        }

        set.add(sb.toString()); // ③
    }

    if (set.size() == m && check(answer, i)) // ④
        answer.add(i);
}

i 는 슈퍼키를 10진수로 표현한 값입니다. 위 예시에서는 1부터 15까지의 수가 가능합니다.

j 는 각 튜플들의 인덱스를 나타냅니다. 위 예시에서는 총 6개의 튜플이 존재하므로, j 는 0부터 5까지의 수가 됩니다.

k 는 각 속성을 순회합니다. 위 예시에서는 0부터 3까지의 수가 됩니다.

위 for 문의 동작 과정은 다음과 같습니다.

1. 먼저 슈퍼키 i를 만듭니다.

2. 그 다음, 해당 슈퍼키로 표현되는 튜플의 속성 값들을 이어 붙여 하나의 문자열을 만듭니다.

3. 만들어진 문자열을 set 에 집어 넣어 유일성 을 판단합니다.

4. set 크기가 튜플의 개수(m) 와 동일하다면, 해당 슈퍼키는 유일성을 만족시킵니다. 또한, check 메소드를 통해 최소성 을 확인합니다. 최소성까지 만족시킨다면, 해당 슈퍼키는 후보키가 될 수 있습니다.

private static boolean check(List<Integer> list, int value) {
    for (int i = 0; i < list.size(); i++) {
        if ((list.get(i) & value) == list.get(i)) return false;
    }

    return true;
}

위의 check 메소드는 최소성을 만족시키는 지 여부를 확인합니다. 위 예시에서, [“학번”] 은 모든 튜플을 유일 하게 식별하며, 또한 최소성 을 만족하므로 후보키로 가능합니다. 따라서, answer 리스트에 들어가게 됩니다.

슈퍼키 [“학번”, “이름”] 도 모든 튜플들을 유일하게 만족합니다. 하지만, 이미 [“학번”] 이 후보키를 만족하므로, [“학번”, “이름”] 은 후보키가 될 수 없습니다. 이 판단을 위의 check 메소드가 수행합니다. 슈퍼키 [“학번”, “이름”] 은 10진수 3으로 표현되고, 이는 이진수 0011 로 표현됩니다. 이미 후보키로 answer 리스트에 추가된 값들을 하나씩 꺼내와, 새로 만든 슈퍼키와 & 연산을 거쳐, 해당 슈퍼키가 더 많은 속성들을 포함하고 있다면 후보 키가 될 수 없습니다.

코드

import java.util.*;

public class Main {
    public static int solution(String[][] relation) {
        int m = relation.length;
        int n = relation[0].length;
        List<Integer> answer = new ArrayList<>();

        for (int i = 1; i < (1 << n); i++) {
            Set<String> set = new HashSet<>();

            for (int j = 0; j < m; j++) {
                StringBuilder sb = new StringBuilder();

                for (int k = 0; k < n; k++) {
                    if ((i & (1 << k)) != 0) sb.append(relation[j][k]);
                }

                set.add(sb.toString());
            }

            if (set.size() == m && check(answer, i))
                answer.add(i);
        }

        return answer.size();
    }

    private static boolean check(List<Integer> list, int value) {
        for (int i = 0; i < list.size(); i++) {
            if ((list.get(i) & value) == list.get(i)) return false;
        }

        return true;
    }

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