[프로그래머스] Level 2. 후보키

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

프로그래머스

 

 

너가어떻게 level 2문제니? 산넘어산이다

1. 모든 가능한 조합 구하기

2. 이 가능한 조합중에서 유일성을 만족하는 키만 추려내기

3. 이 추려낸 키 중에서, 최소성을 만족하는 키 찾기.

 

 

가능한 조합은 combination함수이다. pick.size() == count일 때 원하는 수만큼 조합이 완료된거고, 거기에서 2번을 바로 진행하여 유일성을 만족할 경우에 keys에 넣어준다.

void combination(vector<int>& pick, int index, int count){
    if(pick.size() == count){
        if(IsUniqe(pick)) keys.push_back(pick); //조합이 완성되었을때, 유일성을 만족할 경우 keys에 넣음.
        return;
    }
    
    for(;index<column; index++){
        pick.push_back(index);
        combination(pick,index+1,count);
        pick.pop_back();
    }
}
int solution(vector<vector<string>> relation) {
    column = relation[0].size();
    ::relation = relation;
    
    int answer = 0;
    vector<int> picks;
    //유일성을 만족하는 조합을 찾음.
    for(int i=1; i<=column;i++){
        combination(picks,0,i); //1개조합부터 8개조합까지 모두구함
    }
   //...
    return answer;
}

 

 

 

2. 유일성을 만족하는지 어떻게 아는가. 해당 컬럼의 값들을 모두 a,b,c 형식으로 string화 한다음, set에 넣어줌으로써 확인이 가능하다. set은 동일한 값은 중복해서 넣지 않으므로, set의 개수와 데이터의 개수가 동일해야한다.

bool IsUniqe(vector<int>& pick){
    set<string> s;

    for(int i=0; i<relation.size(); i++){
        string str = "";
        for(int j=0; j<pick.size(); j++){
            str += relation[i][pick[j]]+",";
        }
        
        s.insert(str);
        if(s.size() != i+1) return false;
    }
    
    return true;
}

 

 

3. 최소성을 만족하는지 검사하기.  내 pick의 개수보다 적은 수의 key를 검사한다. 만약 key의 모든 요소가 pick에 있을 경우, pick은 최소성을 만족하지않는다.

bool IsMinimal(vector<int>& pick){
    for(int i=0; i<keys.size(); i++){
        if(keys[i].size() >= pick.size()) continue;
            
        int match = 0;
        for(int j=0; j<keys[i].size(); j++){
            if(find(pick.begin(), pick.end(), keys[i][j]) != pick.end()) match++;     
        }
        
        if(match == keys[i].size()) return false;
    }
    return true;
}

 

 

최종코드

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

using namespace std;

int column = 0;
vector<vector<int>> keys;
vector<vector<string>> relation;


bool IsMinimal(vector<int>& pick){
    for(int i=0; i<keys.size(); i++){
        if(keys[i].size() >= pick.size()) continue;
            
        int match = 0;
        for(int j=0; j<keys[i].size(); j++){
            if(find(pick.begin(), pick.end(), keys[i][j]) != pick.end()) match++;     
        }
        
        if(match == keys[i].size()) return false;
    }
    return true;
}

bool IsUniqe(vector<int>& pick){
    set<string> s;

    for(int i=0; i<relation.size(); i++){
        string str = "";
        for(int j=0; j<pick.size(); j++){
            str += relation[i][pick[j]]+",";
        }
        
        s.insert(str);
        if(s.size() != i+1) return false;
    }
    
    return true;
}
void combination(vector<int>& pick, int index, int count){
    if(pick.size() == count){
        if(IsUniqe(pick)) keys.push_back(pick);
        return;
    }
    
    for(;index<column; index++){
        pick.push_back(index);
        combination(pick,index+1,count);
        pick.pop_back();
    }
}
int solution(vector<vector<string>> relation) {
    column = relation[0].size();
    ::relation = relation;
    
    int answer = 0;
    vector<int> picks;
    //유일성을 만족하는 조합을 찾음.
    for(int i=1; i<=column;i++){
        combination(picks,0,i);
    }
    
    for(int i=0; i<keys.size(); i++){
        if(IsMinimal(keys[i])) answer++;
    }
    

    return answer;
}

 

카카오싫어