문제 링크

문제 간단 해석

후보키가 될 수 있는 조합을 찾되, 유일성과 최소성을 지켜야 한다.

Java

가독성을 위해 기능별로 쪼개보았다. 인스턴스 변수가 조금 많아진 게 흠..

풀이 코드

import java.util.*;

class Solution {
    private int rows;
    private int cols;
    private boolean[] madeBits;
    private boolean[] uncheckBits;
    private Deque<Integer> deque = new ArrayDeque<>();
    private String[][] relation;
    private int answer = 0;

    public boolean isCandidateKey(int now) {
        Set<String> set = new HashSet();
        StringJoiner sj;

        for (int row = 0; row < rows; row++) {
            sj = new StringJoiner(" ");

            for (int col = 0; col < cols; col++)
                if (((now >> col) & 1) == 1)
                    sj.add(relation[row][col]);

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

        if (set.size() == rows) {
            answer++;
            return true;
        }

        return false;
    }

    public void makeDerivedBits(int bit) {
        int now;

        for (int i = 0; i < cols; i++) {
            now = bit | (1 << i);

            if (madeBits[now])
                continue;

            madeBits[now] = true;

            if (uncheckBits[bit] || isCandidateKey(now)) {
                uncheckBits[now] = true;
                deque.addFirst(now);
            } else
                deque.addLast(now);
        }

    }

    public int solution(String[][] relation) {
        this.rows = relation.length;
        this.cols = relation[0].length;
        this.madeBits = new boolean[1 << cols];
        this.uncheckBits = new boolean[1 << cols];
        this.relation = relation;

        int bit;
        deque.addLast(0);

        while (deque.size() > 0) {
            bit = deque.removeFirst();
            makeDerivedBits(bit);
        }

        return answer;
    }
}

해석

int bit;
deque.addLast(0);

while (deque.size() > 0) {
    bit = deque.removeFirst();
    makeDerivedBits(bit);
}

return answer;

먼저 deque에 0을 넣는다. 0에서 비트를 파생시키며 후보키를 찾을 것이다.
deque 맨 앞의 값을 가져와 파생비트를 만든다.

public void makeDerivedBits(int bit) {
    int now;

    for (int i = 0; i < cols; i++) {
        now = bit | (1 << i);

        if (madeBits[now])
            continue;

        madeBits[now] = true;

        if (uncheckBits[bit] || isCandidateKey(now)) {
            uncheckBits[now] = true;
            deque.addFirst(now);
        } else
            deque.addLast(now);
    }

}

기존 비트에서 1개씩 더 활성화한 비트를 파생시킨다.
예를 들면, 0000에서 0001, 0010, 0100, 1000이 만들어진다.

해당 비트들이 과거에 만들어졌었는지 확인한다. 처음 생성된 비트였다면, 다시 생성되지 않도록 madeBits[now] = true;를 걸어준다.

만약 이번에 생성된 비트가 후보키의 조건인 유일성과 최소성을 성립한다면, 파생되는 비트들은 전부 후보키에서 제외되어야 한다.
만약 해당 비트의 부모 객체가 후보키였다면, 해당 비트는 후보키 체크를 하지 않아야 한다.

따라서 uncheckBits[bit] || isCandidateKey(now)로 위와 같은 로직을 지키게 했다.
부모 비트가 후보키였다면 uncheckBits[bit]은 true가 나올 것이다. 따라서 뒤의 isCandidateKey(now)는 동작하지 않을 것이다.
만약 부모 비트가 후보키가 아니라면, isCandidateKey(now)로 후보키인지 확인해본다.

부모 비트가 후보키거나, 이번에 생성된 비트가 후보키였다면 deque의 맨 앞에 넣어 자식 비트들을 최대한 빨리 파생시킨다.
만약 부모 비트도, 현재 비트도 후보키가 아니라면 맨 뒤에 넣는다.

public boolean isCandidateKey(int now) {
    Set<String> set = new HashSet();
    StringJoiner sj;

    for (int row = 0; row < rows; row++) {
        sj = new StringJoiner(" ");

        for (int col = 0; col < cols; col++)
            if (((now >> col) & 1) == 1)
                sj.add(relation[row][col]);

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

    if (set.size() == rows) {
        answer++;
        return true;
    }

    return false;
}

StringJoiner를 통해 해당 비트에 맞는 튜플을 생성해본다.
튜플의 중복을 제거했을 때, size가 전체 row와 같다면 해당 비트는 후보키로 삼을 수 있다.

해당하는 방법으로 후보키를 찾아내며, 찾아낸 후보키의 파생 비트들을 빠르게 생성한 후 모두 후보키로 삼을 수 없게 한다.

Python

비트를 생성 후 후보키들과 비교. 후보키 리스트가 엄청 많아지면 비효율적일 것이라 예상.

풀이 코드

from collections import deque 

def solution(relation):
    total = set([1 << i for i in range(len(relation[0]))])
    impossible = set()
    queue = deque([1 << i for i in range(len(relation[0]))])
    while queue:
        num = queue.popleft()
        
        flag = False
        for imp in impossible:
            if num & imp == imp:
                flag = True
                break
                
        if flag:
            continue
            
        data = set()
        for row in relation:
            data.add(tuple(row[col] for col in range(len(relation[0])) if num & (1 << col)))
        if len(data) == len(relation):
            impossible.add(num)
        else:
            for i in range(len(relation[0])):
                step = 1 << i
                if not num & step and num + step not in total:
                    total.add(num + step)
                    queue.append(num + step)
    
    return len(impossible)

해석

total = set([1 << i for i in range(len(relation[0]))])
impossible = set()
queue = deque([1 << i for i in range(len(relation[0]))])
while queue:
    num = queue.popleft()
...

한 개의 컬럼을 지정하는 total과 queue 생성.
그 후 하나씩 빼온다.

flag = False
for imp in impossible:
    if num & imp == imp:
        flag = True
        break
        
if flag:
    continue

현재 비트가 후보키 비트의 파생이라면(후보키 비트와 현재 비트의 교집합이 후보키 비트와 같다면) 더 처리하지 않고 다음 비트를 가져온다.

data = set()
for row in relation:
    data.add(tuple(row[col] for col in range(len(relation[0])) if num & (1 << col)))
if len(data) == len(relation):
    impossible.add(num)
else:
    for i in range(len(relation[0])):
        step = 1 << i
        if not num & step and num + step not in total:
            total.add(num + step)
            queue.append(num + step)

해당 비트로 튜플을 만들어 비교. 만약 후보키라면 impossible에 추가한다.
후보키가 아니라면 파생 비트를 생성한다. 파생 비트가 지금까지 만들어진 비트가 아니라면 total과 queue에 추가한다.

여담

후보키.. 후보키.. 후보키..
게슈탈트 붕괴가 일어났다..

근데 게슈탈트 붕괴를 우리말로 의미 포화라 부른다는데, 현실에서 쓰는 사람을 한 번도 못본 것 같다.