[프로그래머스][level2] 후보키 (C++)

https://programmers.co.kr/learn/courses/30/lessons/42890

코딩테스트 연습 - 후보키

 

 

[난이도] level2
[유형] 브루트포스

[풀이]
칼럼의 수 N이 8개, 로우가 20개이므로 모든 키의 조합에 대해 확인해봐도 시간내에 해결이 가능합니다.
N이 8이기때문에 bit연산을 이용하였습니다.
예를들어 0101이 후보키라면 0111은 최소성을 만족하지 못하므로 후보키가 될 수 없다는 것을 이용하였습니다.

1) 1~(2^N-1) 까지 키의 조합이 될 수 있는 모든 경우를 돌면서
몇개의 속성을 사용하는지에 따라 각각의 bitmasks 배열에 넣어줍니다.
ex) 11010 이라면 3개를 사용하므로 bitmasks[3]에 push
개수별로 나눠서 저장하는 이유는 bitmasks[1]부터 속성을 적게 사용하는 것부터 candidates로 분류해놔야
많은 속성을 사용하는 것들이 최소성을 만족하는지 체크할 수가 있습니다.
(다른 풀이를 보니 개수별로 분류하지 않고 1~2^N-1까지 순서대로 체크해도 문제가 없다는 것을 알 수 있었습니다. 예를들면 10101 10001보다 무조건 뒤에 오기 때문입니다.)

2) 가장 작은 속성을 사용하는 bitmasks[1] vector의 값들부터 순회하면서
현재 나온 값이 후보키가 될 수 있는지를 체크합니다.

[최소성 체크]
isExist() 함수는 이미 앞에 나온 후보키들에 의해 현재 확인중인 비트마스크가 후보키가 될 수 있는지를 체크합니다. 만약 현재 체크하는 값이 10101인데 후보키를 저장하는 cand에 10001이 들어있다면 isExist는
true를 return하며 종료합니다.
10101과 10001의 bit and 연산으로 간단히 포함관계인지 체크할 수 있습니다.
(10101 & 10001) == 10001 -> bit 연산 후에도 10001의 값을 유지한다는 것은 모든 bit가 현재 체크하는 값에서
살아있다는 의미이므로 이 둘은 포함관계입니다.

[유일성 체크]
isExist()가 false라면 그다음엔 현재 체크중인 bitmask로 유일성을 만족하는지 체크해야 합니다.
check() 함수에서 모든 relation을 순회하면서 masking된 속성의 string을 전부 이어붙힙니다.
주의할점이 그냥 이어붙히면 [A,AA] [AA,A]를 동일하게 인식하므로 "#"를 속성 뒤에 붙혀서 구분을 해주었습니다.
완성된 string을 set에 넣습니다. 만약 이미 string이 들어있다면 유일성을 만족하지 못하는 것이므로 false를 return 합니다.

3. 위 과정에서 !isExist() && check()를 만족하는 것들만 후보키로 등록되게 되며 이 개수를 return하면 정답입니다.

 

#include <string>
#include <vector>
#include <cstdio>
#include <set>
using namespace std;
int N;
vector<int> bitmasks[9],cand;
vector<vector<string>> relation;
bool check(int bitmask){
    set<string> s;
    vector<int> flag(9);
    for(int i=0;i<N;i++){
        if(bitmask&(1<<i)) flag[i]=1;
    }
    for(auto rel : relation){
        string tmp;
        for(int i=0;i<N;i++){
            if(flag[i]) tmp+=(rel[i]+"#");
        }
        if(s.find(tmp)!=s.end()) return false;
        s.insert(tmp);
    }
    return true;
}
bool isExist(int bm){
    for(auto v : cand){
        if(v == (v&bm)) return true;   
    }
    return false;
}
int solution(vector<vector<string>> _relation) {
    relation=_relation;
    int answer = 0;
    N=relation[0].size();

    for(int i=1;i<(1<<N);i++){
        int cnt=0;
        for(int j=0;j<N;j++){
            if((i&(1<<j))>0) cnt++;
        }
        bitmasks[cnt].push_back(i);
    }
    for(int i=1;i<=N;i++){
        for(auto bm : bitmasks[i]){
            if(!isExist(bm)){
                if(check(bm)) {
                    cand.push_back(bm);
                    answer++;
                }
            }
        }
    }
    return answer;
}

 

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/후보키.cpp