[2019 KAKAO BLIND RECRUITMENT] 후보키

문제풀이

크게 문제풀이는 유일성을 확인 -> 유일성을 만족하는 것중 최소성을 만족하는것을 구하기 순으로 풀이하였습니다.

비트마스크를 이용하였고 비트마스크를 적용하니 이전보다 문제풀이가 훨씬 깔끔해졌습니다.

 

1. 유일성 확인방법

vector<string>을 키로가지는 Set을 만들어 여러 경우의 키를 가지는 경우를 넣어서 

set 의 사이즈가 레코드의 개수와 같을때 유일하다 판단합니다.

여기서 키로 선택된 칼럼은 비트로 1 아닌건 0으로해서 계산하는데

유일성이 만족되면 해당 값을 벡터에 저장합니다.

 

2. 최소성확인방법

유일성을 만족하는 벡터를 차례로 돌며 & 연산을 진행합니다.

a == a&b 일때

a는 b의 부분집합입니다.

그래서 b는 최소성을 만족할수 없기때문에 제외시킵니다.

이와같은 방법으로 모두 비교하여 최소성을 만족하는 것들의 수를 구합니다.

소스코드

#include <string>
#include <vector>
#include <set>
 
using namespace std;
int n_column;
int mask;
 
bool isUnique(int bit,vector<vector<string>> relation){
    set<vector<string>> check_set;
    for(int i=0;i<relation.size();i++){
        vector<string> keys;
        for(int j=0;j<n_column;j++){
            if(bit &(mask>>j)){//넣는곳일때
                keys.push_back(relation[i][j]);
            }
        }
        check_set.insert(keys);
    }
    if(relation.size() == check_set.size())
        return true;
    return false;
}
int solution(vector<vector<string>> relation) {
    int answer = 0;
    n_column = relation[0].size();
    mask = 1<<(n_column-1);
    
    vector<int> uniques;
    vector<bool> check_minimality;
    
    for(int i=1;i<(1<<n_column);i++){
        if(isUnique(i, relation))
            uniques.push_back(i);
    }
    
    check_minimality.assign(uniques.size(), true);
    
    for(int i=0;i<uniques.size()-1;i++){
        for(int j=i+1;j<uniques.size();j++){
            if(uniques[i]==(uniques[i]&uniques[j])){//uniques[i]가 부분집합일때
                check_minimality[j] = false;
            }
            else if(uniques[j]==(uniques[i]&uniques[j])){//uniques[j]가 부분집할일때
                check_minimality[i] = false;
            }
        }
    }
    
    for(int i=0;i<check_minimality.size();i++){
        if(check_minimality[i])
            answer++;
    }
    
    return answer;
}

 

문제 링크 : www.programmers.co.kr/learn/courses/30/lessons/42890

프로그래머스