Array ( )

2019 카카오 신입 공채 1차 코딩 테스트 풀이 - 3번문제

2018-10-02 01:47:08 | 조회수 2601


3번 문제는 정답률이 확 떨어지는 만큼 까다로운 문제입니다. 문제는 후보키를 구하는 문제인데, 후보키는 유일성과 최소성을 만족해야 한다고 합니다. 즉, A가 후보키라면 AB, AC는 후보키가 될 수 없다는 뜻이 됩니다.


여기서 집합의 원리를 비트연산자를 이용해 구현할 수 있습니다. i 번째 원소가 후보키 집합의 원소라면 1, 아니라면 0으로 비트를 설정한 숫자가 있을 때, 최소성을 가지는 가지는 수는 다른 후보키와 AND 연산을 했을 때 자기 자신이 나오게 됩니다.


좀 더 자세히 설명하면, 1(0001) 과 3(0011) 이 있을 때, $ 1&3 = 1$ 이므로, 1이 최종적인 후보키가 됨을 알 수 있습니다.


i번째 튜플이 후보키 집합에 포함 되냐 되지 않느냐를 체크해야 하는데, 튜플의 개수는 8개이므로 $2^8$ 가지만 체크해보면 됩니다. 즉, 모든 경우의 수를 빠르게 체크할 수 있습니다.


그러므로 i번째 원소가 포함 되는 경우, 안 되는 경우를 재귀함수로 구현하여 호출하면서, 후보키 후보가 나왔을 때 비트 연산자를 통하여 최소성을 만족하면 정답이 됩니다. 최종적으로 그런 후보키들을 저장하고 있는 배열의 크기를 반환합니다.


※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.

#include <string>
#include <set>
#include <vector>
using namespace std;

vector<int> cdt;

void dfs(int idx, int bit, vector<vector<string> > &relation) {
    if (idx == relation[0].size()) {
        return;
    }
    set<string> cmp;
    for (int i = 0; i<relation.size(); i++) {
        string key;
        for (int j = 0; j<relation[i].size(); j++) {
            if ((bit & (1 << j))) {
                key += relation[i][j];
            }
        }
        cmp.insert(key);
    }
    if (cmp.size() == relation.size()) {
        bool f=true;
        for (int i = 0; i<cdt.size(); i++) {
            if ((cdt[i] & bit) == cdt[i]) {
                f=false;
                break;
            }
            if ((cdt[i] & bit) == bit) {
                f=false;
                cdt[i] = bit;
                break;
            }
        }
        if(f) {
            cdt.push_back(bit);
        }    
    }
    dfs(idx + 1, bit, relation);
    dfs(idx + 1, (bit | (1 << (idx + 1))), relation);
}

int solution(vector<vector<string>> relation) {
    dfs(0, 0, relation);
    dfs(0, 1, relation);

    return cdt.size();
}


2019 카카오 신입 공채 1차 코딩 테스트 풀이 - 3번문제 - 알고리즘닷컴
32 개의 글