[알고리즘C++]후보키

오늘의 문제

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

후보키

나의 풀이

#include <string>
#include <vector>
#include <set>

using namespace std;
vector<int> per;   
set<string> perSet;              
bool check[9] = { false, };        
vector<string> uni;
int cou = 0;

void permutation(int depth, int n, int idx, vector<vector<string>>rel){   
    
    if(depth == n){ 
        perSet.clear();
        for(int i=0;i<rel.size();i++){ // 유일성 검사
            string s ="";
            for(int j=0;j<n;j++)
                s+= rel[i][per[j]];
            if(perSet.insert(s).second == false)
                return;
        }
        string s = ""; // 최소성 검사
        for(int i=0;i<per.size();i++){
            s+= to_string(per[i]);
        }
        for(int i=0;i<uni.size();i++){
            int c = 0;
            for(int j=0;j<uni[i].size();j++){
                if(s.find(uni[i][j]) != string::npos){
                c++;
                }
            }
            if(c == uni[i].size())
                return;
        }
        uni.push_back(s);
        cou++;
        return;
    }
    for(int i = idx; i < rel[0].size(); i++){   
        if(!check[i]){
            check[i] = true;
            per[depth] = i;          
            permutation(depth + 1, n, i+1, rel);   
            check[i] = false;          
        }
    }
}

int solution(vector<vector<string>> relation) {
    // 유일성은 중복 없는것
    // 최소성은 그보다 속성이 작은 유일성만족 후보키가 없는것
    int cmp = 1;
    while(relation[0].size() >= cmp){
        vector<int> p(cmp, 0);
        per = p;
        permutation(0, cmp, 0, relation); // 조합
        cmp++;
    }
    return cou;
}

모범 답안

#include <bits/stdc++.h>
 using namespace std;
bool possi(vector<int> &vec,int now){
    for(int i=0;i<vec.size();i++)
        if((vec[i]&now)==vec[i])return false;
    return true;
}
int solution(vector<vector<string>> relation) {
    int n=relation.size();
    int m=relation[0].size();
    vector<int> ans;
    for(int i=1;i<(1<<m);i++){
        set<string> s;
        for(int j=0;j<n;j++){
            string now="";
            for(int k=0;k<m;k++){
                if(i&(1<<k))now+=relation[j][k];
            }
            s.insert(now);
        }
        if(s.size()==n&&possi(ans,i))ans.push_back(i);
    }
    return ans.size();
}

배울 점

• 하.. 코테였으면 테스트만 해보고 와 다풀었다 ^ㅅ^하고 넘겼을 문제.. core dump가 나는것도 모르고 제출했을 것이다. 재귀에서 특이조건에서만 return을 안해주니 오류가 날수밖에
• 더 꼼꼼하게 풀자
• 모범답안 뭐냐.. 현타 비트연산을 쓰냐