프로그래머스 - 후보키

프로그래머스 - 후보키

단순 구현 문제로 map을 쓸줄알고, 문자열 포함 여부만 잘 체크해주면 된다.
일단 총 4개의 컬럼이 존재한다고 가정하면,
0, 1, 2, 3
0 1, 0 2, 0 3, 1 2, 1 3, 2 3
0 1 2, 0 1 3, 0 2 3, 1 2 3
0 1 2 3
으로 총 15가지의 경우가 존재한다.
이 조합을 먼저 구하고, 해당 조합에 대해서 Key를 만들고 map을 이용해서 중복 체크만 해주면 된다.
문제의 예시에서 예를 들어 0 1이면 "100_ryan" 으로 문자열을 치환해서 map에서 중복체크를 해주면 된다.

이렇게 모든 조합에 대해서 수행하면 최소성을 고려하지 않은 모든 후보키들이 구해진다.

해당 후보키들에 대해서 최소성을 고려해줘야 하는데, 예를 들어 (0 1)번째를 혼합한 후보키가 있을 때, (0 1 2)번째를 혼합한 후보키는 최소성을 만족하지 않기 때문에 이는 빼줘야 한다.
또한 (0 2)번째를 혼합한 후보키가 있을 때도 (0 1 2)번째를 혼합한 후보키는 최소성을 만족하지 못한다.
모든 후보키를 다 구한 뒤 위와 같은 케이스를 제외해주고, 남은 후보키들이 정답의 갯수가 된다.

코드는 아래와 같다.

#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

int candidate[128];
int visit[128];
int relation_size;
vector<vector<string>> relations;
vector<vector<int>> result_set;

void bfs(int n, int depth, int type)
{
    if(depth == n) {
        map<string, int> m;
        int cnt = 0;
        for(int i=0;i<relation_size;i++) {
            string s = "";
            for(int j=0;j<n;j++) 
                s += relations[i][candidate[j]] + "_";
            
            if(m.find(s) == m.end()) {
                cnt++;
                m.insert( {s, 0} );
            }
        }
        if(cnt == relation_size) {
            vector<int> tmp;
            for(int i=0;i<n;i++)
                tmp.push_back(candidate[i]);
            result_set.push_back(tmp);
        }
        
        return;
    }
    
    for(int i=0;i<type;i++) {
        if(visit[i] || i < candidate[depth - 1])
            continue;
        visit[i] = 1;
        candidate[depth] = i;
        bfs(n, depth + 1, type);
        visit[i] = 0;
    }
}
int solution(vector<vector<string>> relation) {
    int answer = 0;
    int type = relation[0].size();
    relation_size = relation.size();
    relations = relation;
    
    for(int i=0;i<type;i++) 
        visit[i] = 0;
    
    for(int i=1;i<=type;i++) {
        vector<vector<int>> key;
        bfs(i, 0, type);
    }
    
    map<string, int> m;
    for(int i=0;i<result_set.size();i++) {
        string s = "";
        for(int j=0;j<result_set[i].size();j++) 
            s.push_back(result_set[i][j] + '0');
        m[s] = 0;
    }
        
    for(int i=0;i<result_set.size();i++) {
        string s = "";
        for(int j=0;j<result_set[i].size();j++) 
            s.push_back(result_set[i][j] + '0');
        
        m[s]++;
        for(int j=i+1;j<result_set.size();j++) {
            string tmp = "";
            for(int k=0;k<result_set[j].size();k++) 
                tmp.push_back(result_set[j][k] + '0');
            
            int cnt = 0;
            for(int p=0;p<s.size();p++) 
                for(int k=0;k<tmp.size();k++) 
                    if(s[p] == tmp[k])
                        cnt++;

            if(cnt == s.size()) 
                m[tmp]++;
        }
    }
    
    for(auto it : m)
        if(it.second == 1) 
            answer++;
        
    return answer;
}