후보키

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

코딩테스트 연습 - 후보키

 

후보키 - 유일성과 최소성이 만족하는 키를 구해야한다. 

 

처음에 아래와 같이 풀었는데 채점이 통과 되질 않았다. 그리고 너무 코드가 길다는 생각을 했음. 

<1번 코드>(테스트 통과X)

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

using namespace std;


bool iscandidate(vector<string>v){
    map<string,bool>m;
    for(int i=0; i<v.size(); i++){
        if(m[v[i]]==true){return false;}
        m[v[i]]=true;
    }
    return true;
}

vector<string> sumeachother(vector<int>&sumwhat,vector<vector<string>>&allclmlist){
   vector<string>sumlist;
    for(int i=0; i<sumwhat.size(); i++){
        int clmn = sumwhat[i];
        if(i==0){sumlist = allclmlist[clmn]; continue;}
        vector<string>result;
        transform( sumlist.begin(), sumlist.end(), allclmlist[clmn].begin(), std::back_inserter(result), std::plus<string>() );
        sumlist = result; 
    }
    for(int i=0; i<sumlist.size(); i++){
        cout<<sumlist[i]<<" ";
    }
    cout<<endl;
    return sumlist;
}



int solution(vector<vector<string>> relation) {
    int answer = 0;
    int clmn= relation[0].size();
    int studentnum = relation.size();
    map<int,bool>candicheck;
    vector<vector<string>> allclmlist(clmn);
    vector<int>notcandi;
    for(int i=0;i<clmn;i++ ){
        vector<string> clmnlist;
        for(int j=0; j<studentnum; j++){
            clmnlist.push_back(relation[j][i]);
        }
        if(iscandidate(clmnlist)==true){ answer++; candicheck[i]=true;}
        else{notcandi.push_back(i);}
        allclmlist[i]=clmnlist;
    }
    //조합으로 풀기 
    int n = notcandi.size();
  
    for(int i=2; i<=n; i++){
          vector<int>combi(n,0);
        for(int j=0;j<i; j++){
            combi[j]=1;
        }
        do{
            vector<int>sumwhat;
            bool toggle = true;
          /*   for(int k=0; k<combi.size();k++){
                 cout<<combi[k]<<" ";
             }
            cout<<endl;*/
            for(int k=0; k<combi.size();k++){
                if(candicheck[notcandi[k]]==true){ toggle = false;break;}
                if(combi[k]==1 && candicheck[notcandi[k]]==false ){
                    sumwhat.push_back(notcandi[k]);
               }
              }
             if(toggle==false){continue;}
             if(iscandidate(sumeachother(sumwhat,allclmlist))==true){
                for(int p=0; p<sumwhat.size(); p++){
                        candicheck[p]=true;
                    }
                     answer++;
                }
            
        }while(prev_permutation(combi.begin(),combi.end()));
       
    }
    

        return answer;
}

 

찾아보니까 대부분 비트마스크로 푸는 것을 발견했다.

<2번 코드>(테스트 모두 통과한 코드)

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
#include <functional>
#include<set>

using namespace std;


bool iscandidate(vector<int>v , int key){
    for(int i=0; i<v.size(); i++){
        if((v[i]&key)==v[i]){return false;}
    }
    return true;
}


int solution(vector<vector<string>> relation) {
    int answer = 0;
    int clmn= relation[0].size();
    int row = relation.size();
    vector<int>ans;
  
    for(int i=1; i<(1<<clmn); i++){ 
    /*
     1(0001) - 학번
     2(0010) - 이름
     3(0011) - 이름, 학번
     4(0100) - 전공
     5(0101) - 학번, 전공
     6(0110) - 이름, 전공
     7(0111) - 학번, 이름, 전공
     8(1000) - 학년
     9(1001) - 학번, 학년
     10(1010) - 이름, 학년
     11(1011) - 학번, 이름, 학년
     12(1100) - 이름, 학번
     13(1101) - 학번, 전공, 학년
     14(1110) - 이름, 전공, 학년
     15(1111) - 학번, 이름, 전공, 학년
     */
        set<string>s; // 중복이 있을 수가 없다. 그래서 실제로 중복이 생기는 경우 (s의size < 행의개수)
            for(int j=0; j<row; j++){
                string sum="";
             
                    for(int k=0; k<clmn; k++){ //비트마스크결과 1이 나오는 column의 값을 각행에서 더해준다.
                           if(i&(1<<k)){
                        sum+=relation[j][k]; 
                         }
                    }
                 s.insert(sum);       
            }
         if(s.size()==row && iscandidate(ans,i)){ans.push_back(i);} //row의 size와 같은지 파악하고 이미 나온 후보키인지 확인
    }
    answer = ans.size();
        return answer;
}

비트마스크로 푸는게 유일성을 파악하는데 훨씬 쉽다. 그리고 위에 <1번 코드>조합으로 푼 경우에서 틀린이유는 [키A, 키B] 가 후보키라면 [키A, 키C]도 후보 키 조건에 맞는 것이다. 하지만 나는 키A 가앞서 후보키로 포함이 돼서 [키A, 키C] 는 후보키가 안되는 줄 알았다. 문제조건을 잘못 파악했던 것 같다. 위의 <1번 코드>는 이부분만 고치면 되지만 비트마스크로 푸는게 훨씬 효율적이어 보여 비트마스크로 풀게 되었다.