lv2 후보키

레벨 2중에서 구현난이도만 봤을때는 최종보스이다.

결국에 시간을 많이 들여서 풀긴 풀었다.

 

 

제일 시간이 오래걸린 곳 : 문제를 잘못읽었다.

후보 키의 최대 개수를 구하라. -> 후보키 칼럼의 최대 개수로 읽어서 여기서 너무 오래 걸렸다. 

즉, 나는 후보키 는 "학번" = 1 , "이름, 전공" = 2 해서 max() 값인 2가 나오는건데

이것이 아니라 후보키의 개수를 그냥 구하는 것이다....

 

 

일단 후보키 후보를 구해보자. 예를 들어서

학번, 이름, 전공, 학년 => 총 4개의 칼럼이 있다.

 

그러면 후보키 후보는

학번

이름

전공

학년

학번 이름

학번 전공

학번 학년

이름 전공

이름 학년

학번 이름 전공

학번 이름 학년

학번 전공 학년

이름 전공 학년

학번 이름 전공 학년 

이다.

85~88줄이다.

그면 여기서 의문점.. 유일성과 최소성을 어떻게 체크할 것인가???

ex) (학번 이름 전공) 칼럼 그룹이 유일성과 최소성을 만족하는지 체크해보자.

 

 

유일성은 학번 문자열+이름 문자열 + 전공 문자열 을 이어붙여서 map에다가 넣는데

만약에 이 이어붙인 문자열이 중복으로 존재한다? => 유일성이 모순되므로 후보키에서 탈락

13~37줄이다.

 

최소성은 칼럼에서 하나씩 뺀 (학번, 이름 / 학번, 전공 / 이름, 전공)이

전부 다 유일성을 가지면 안된다.

하나라도 유일성을 가지면 최소성이 모순되므로 후보키에서 탈락된다.

 

만약 학번문자열+이름문자열 을 이어붙여서 map에다가 넣는데 만약에 이 이어붙인 문자열에 중복이 없다?

그러면 학번+이름이 학번+이름+전공 의 최소성을 씹어버린다.

41~71줄이다.

 

 

 

 

 

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
 
int check[8] = { 0 };
int ans = 0;
 
void make(vector<vector<string>> arr, int cur_pos, int cnt)
{
    if (cur_pos == arr[0].size()) // 유일성 체크
    {
 
        map<string, int> m;
        for (int i = 0; i < arr.size(); i++)
        {
            
            string tmp = "";
            for (int j = 0; j < arr[0].size(); j++)
            {
                if (check[j] == 1)
                    tmp += arr[i][j];
            }
            if (m[tmp] == 0)
                m[tmp] = 1;
            else
                return;
 
        }
 
        if (cnt == 1)
        {
            ans++;
            return;
        }
 
 
        m.clear();
        for (int i = 0; i < cur_pos; i++) // 최소성 체크
        {
            if (check[i] == 0)
                continue;
            check[i] = 0;
            map<string, int> mm;
            int is_candi = 1; // candi가 되면 안돼..
            
        
            for (int j = 0; j < arr.size(); j++)
            {
                string tmp = "";
                for (int k = 0; k < arr[j].size(); k++)
                {
                    if (check[k] == 1)
                        tmp += arr[j][k];
                }
                if (mm[tmp] == 0)
                    mm[tmp] = 1;
                else
                {
                    is_candi = 0;
                    break;
                }
 
            }
            check[i] = 1;
            if (is_candi == 1)
                return;
            
        }
        
        /*
        for (int i = 0; i < arr[0].size(); i++)
            cout << check[i] << ' ';
        cout << '\n';
        */
        
        ans++;
        return;
    }
    
 
 
    check[cur_pos] = 1;
    make(arr, cur_pos + 1, cnt + 1);
    check[cur_pos] = 0;
    make(arr, cur_pos + 1, cnt);
 
}
 
 
 
 
int solution(vector<vector<string>> arr)
{
 
    make(arr, 0, 0);
    return ans;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
 
    /*
    vector<vector<string>> str = { 
    {"100", "ryan", "music", "2"},
    {"200", "apeach", "math", "2"},
    {"300", "tube", "computer", "3"},
    {"400", "con", "computer", "4"},
    {"500", "muzi", "music", "3"},
    {"600", "apeach", "music", "2" }};
    
 
    vector<vector<string>> str = {
    {"100", "abc", "1"},
    {"100", "abd", "2"},
    {"100", "abd", "4"},
    {"200", "abc", "2"},
    {"200", "abd", "1"},
    {"200", "abd", "3"},
    };
    */
    vector<vector<string>> str = {
        {"b","2","a","a","b"},
        {"b","2","7","1","b"},
        {"1","0","a","a","8"},
        {"7","5","a","a","9"},
        {"3","0","a","f","9"},
    };
    cout << solution(str);
 
}