[카카오 코딩 테스트] 후보키

https://www.welcomekakao.com/learn/courses/30/lessons/42890

코딩테스트 연습 - 후보키 | 프로그래머스

꽤 어려운 문제였다. 처음에 문제를 이해하기가 어려워서 결국 답을 참고하긴 했지만 이 문제에서 여러가지를 배울 수 있었다. 어트리뷰트를 선택할 때, 비트를 사용해 문제에 나온 예를 사용한다면 0000부터 1111까지 검사를 한다. key를 만들땐,

 if ((bit & (1 << j))) {

      key += relation[i][j];

 }

로 string에 더해줬고, 그 키를 set에 넣어 중복을 없애 줬다. 중복이 되는 키를 없앴기 때문에 set에 들어있는 갯수와 relation에 들어있는 갯수가 같으면 최소성 검사를 했다.

#include<string>
#include <vector>
#include<set>
using namespace std;
 
vector<int> cdt;
void dfs(int bit, vector<vector<string> > &relation) {
    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) {
                vector<int>::iterator iter;
                iter = cdt.begin() + i;
                cdt.erase(iter);
                i--;
            }
        }
        if (f) {
            cdt.push_back(bit);
        }
    }
}
 
int solution(vector<vector<string>> relation) {
    int t = 1 << relation[0].size();
 
    for(int i = t - 1; i > 0; i--)
        dfs(i, relation);
 
    return cdt.size();
}