[Programmers] 후보키

문제 : programmers.co.kr/learn/courses/30/lessons/4289

2019 KAKAO BLIND RECRUITMENT

---

bitmask bitmasking

[ 문제해석 ]

 

 속성의 모든 부분 집합 중, 유일성과 최소성을 만족하는 집합을 찾아야한다.

 이때, 유일성은 해당 집합의 속성 값들로 튜플을 구분할 수 있으면 되고, 최소성은 유일성을 만족하는 속성 집합 중에서 하나라도 속성이 빠지면 유일성이 깨지는 경우를 말한다.

 

[ 알고리즘풀이 ]

 

 우리가 다뤄야 될 속성은 최대 8개이므로 bitMask를 이용해서 가능한 모든 속성 조합을 다룰 수 있다.

 예를 들어, 1011(2) = 13 이라는 값은 0번, 1번, 3번 속성을 선택한 경우라고 생각하자.

 그러면, M개의 속성이 있다고 가정하면 (1 ~ 2^M - 1) 값들이 공집합을 제외한 모든 부분 집합을 의미한다.

 

 1) 가능한 모든 속성 집합을 순회하며 유일성을 체크하자.

 

 유일성을 만족한다는 것은 결국 모든 튜플 쌍들에 대해서 현재 속성으로 구분이 가능하다는 뜻이다. 따라서, getBit 함수를 통해 속성들의 index를 얻어내고, 모든 튜플 쌍들에 대해 현재 속성들로 값이 구분되는지 ( 다른 값이 있는지 ) 체크한다.

 

 2) 유일성이 검증된 애들 중 최소성을 체크하자.

 

 최소성은 결국 1번, 2번, 5번 속성으로 유일성을 만족했다면 1번 / 2번 / 5번 / 1번, 2번 / 1번, 5번 / 2번, 5번 으로는 유일성을 만족하지 못해야된다.

 따라서, 유일성을 만족한 애들 중 속성의 갯수를 기준으로 sorting을 한 다음 현재 내가 선택한 속성보다 속성의 갯수가 작은 경우 중 나의 부분 집합이 있는지 체크하면 된다.

 부분집합은 & 연산을 통해서 간단하게 체크가 가능하다.

 예를 들어, 1011과 0011 은 부분집합 관계이므로 1011 & 0011 = 0011 이 성립한다.

 

 

[ C++ 코드구현 ]

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<int> getBit(int x) {
    vector<int> v;
    int index = 0;
    while (x) {
        if (x % 2) v.push_back(index);
        x /= 2;
        index++;
    }
    return v;
}
 
int getBitCount(int x) {
    int ans = 0;
    while (x) {
        if (x % 2) ans++;
        x /= 2;
    }
    return ans;
}
 
bool compare(int A, int B) {
    return getBitCount(A) <= getBitCount(B);
}
 
int solution(vector<vector<string>> relation) {
    int N = relation.size(), M = relation[0].size();
    int maxSize = (1 << M);
 
    vector<int> bitMask;
    for (int i = 1; i < maxSize; i++) {
        vector<int> cols = getBit(i);
        
        bool isBit = true;
        for (int j = 0; j < N; j++) {
            for (int k = j + 1; k < N; k++) {
                bool isDif = false;
                for (int l = 0; l < cols.size(); l++) {
                    if (relation[j][cols[l]] != relation[k][cols[l]]) {
                        isDif = true;
                    }
                }
                if (!isDif) 
                    isBit = false;
            }
        }
        if (isBit) bitMask.push_back(i);
    }
    
   sort(bitMask.begin(), bitMask.end(), compare);
    
    int ans = 0;
    for (int i = 0; i < bitMask.size(); i++) {
        bool isAns = true;
        for (int j = 0; j < i; j++) {
            if ((bitMask[i] & bitMask[j]) == bitMask[j]) isAns = false;
        }
        if (isAns) ans++;
    }
    return ans;
}

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/Programmers/%ED%9B%84%EB%B3%B4%ED%82%A4.cpp

travelbeeee/ProblemSolving

---