프로그래머스 - 후보키(C++)

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

프로그래머스

 

조합과 0123이 들어왔을 때 023을 찾아낼 수 있는가? 라는 문제와 같다.

 

그래서 각 튜플을 문자열을 이어붙이고 set을 사용해 유일성을 판단하고

각 후보키들을 배열에 넣어놓고

현재 후보키의 후보를 0123이 들어왔을 때 

 

023을 가져와서 임시 배열의 0, 2, 3을 true로 만든다.

그리고 0,1,2,3을 거쳐 임시 배열이 true인 것의 개수를 샌다. 만약 카운트의 수 = 지금 비교하고 있는 후보키의 길이 이면 이것을 유일성을 지키지 않은 것이 된다.

 

그런데 난 여기서 반례를 하나 찾았다.

 

이름	나이	학번
AB	C	D
A	BC	E
A	C	I

 

라고 하자, 이름과 나이는 중복이 있으므로 후보키가 될 수 없다. 

학번은 후보키가 될 수 있다.

그리고 이름이 A이고 나이가 BC인 것과, 이름이 AB이고 나이가 C인 것은 엄연히 다른 것이므로 이것을 구분해야한다. 만약 단순히 문자열을 이어붙이는 방식으로 코드를 짜면 위의 경우 유일성을 위배한다고 판단해버릴 것이다. 

 

그래서 문자열 사이에 ' | ' 같은 구분자를 넣어주는 것이 좋아보인다.

 

#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <iostream>
using namespace std;

vector<int> now_key;
vector<vector<int>> keys;
vector<vector<string>> rel; 
bool combination_check[21];

int answer = 0;
bool uni_check(){
    set<string> s;
    
    for (int i = 0; i < rel.size(); i++){
        string tmp = "";
        
        for(int j = 0; j < now_key.size(); j++){
            tmp += (rel[i][now_key[j]] + '*');
        }
        
        s.insert(tmp);
    }
    
    if(s.size() == rel.size()) return true;
    else return false;
}

bool min_check(){
    // 후보키로 012가 들어왔을 때 만약 02 가 이미 후보키라면 불가능함
   for(int i = 0; i < keys.size(); i++){
       bool check[21];
       for(int j = 0; j < 21; j++) check[j] = false;
       
       for(int j = 0; j < keys[i].size(); j++){
           check[keys[i][j]] = true;
       }
       
       int cnt = 0;
       for(int j = 0; j < now_key.size(); j++){
           if(check[now_key[j]]) cnt++;
       }
       
       if(cnt == keys[i].size()) return false;
   }
    
    return true;
}

void dfs(int idx, int cnt, int lim){
    if(cnt == lim){
        if(uni_check() && min_check()){
            keys.push_back(now_key);
            
            // for(int a : now_key){
            //     cout << a << ' ';
            // }
            cout << endl;
            answer++;
        }
        
        return;
    }
    
    for(int i = idx; i < rel[0].size(); i++){
        if(combination_check[i]) continue;
        
        combination_check[i] = true;
        now_key.push_back(i);
        dfs(i, cnt + 1, lim);
        now_key.pop_back();
        combination_check[i] = false;
    }
}

int solution(vector<vector<string>> relation) {
    rel = relation;
    
    for(int i = 1; i <= relation[0].size(); i++){
        dfs(0, 0, i);
    }
    
    return answer;
}