[C++] level2 후보키 42890

참고자료
해당 문제는 구글링을 통해 해결하였으므로 참고한 블로그를 상단에 첨부한다.
https://velog.io/@huijae0817/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98C%ED%9B%84%EB%B3%B4%ED%82%A4

📌후보키

/* 해당 문제 설명은 링크로 대체한다. */

📌풀이

먼저 후보키를 구하기 위해선 유일성과 최소성을 만족하는 조합을 찾아야한다.
그래서 내가 처음 생각해 낸 방식은 조합을 이용한 방식이다.
0, 1, 2라는 값이 있다면,
0에 대하여 0, 01,02, 012 이렇게 해서 가능한 모든 집합을 찾고,
처음에 가능한 조합을 next_permutation()만들어서 유일성은 확보하였지만, 최소성을 만족시키는 법을 찾지 못했다.

어려워

어떤 식으로 유일성과 최소성을 만족시켜야 할지 모르겠어서 결국 구글링을 통해 해결하였다.

아래 코드는 벨로그 후이재님의 코드인데, 이걸 통해 set.insert(value).second가 무엇인지,
string::npos에 대해서 알게되었다.
중복되면 안되는 성질을 이용하여 set을 사용한 것도 좋은 방법인 것 같다....

📌코드

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

using namespace std;
vector<int> per;    //검사해야 할 칼럼들을 담아 둔 vector
set<string> perSet; //유일성을 만족하는지 확인하기 위한 set(중복 x)       
bool check[9] = {false, };   //칼럼 check용 ... relation의 칼럼의 길이는 8이하이므로 9로 초기화     
vector<string> uni; //유일성과 최소성을 만족하는 후보키를 담아두는 vector

void permutation(int depth, int n, int idx, vector<vector<string>>rel){   
    if(depth == n){ 
        //1. 유일성 검사
        perSet.clear(); //초기화 

        for(int i = 0; i < rel.size(); i++){  //행을 반복하며 돌음
            string s ="";
            for(int j = 0; j < n; j++)
                s += rel[i][per[j]]; //가능한 조합을 s로 만들어
            //만약 insert 실패하면 return (실패했다는 것은 이미 존재 == 유일성 만족 X)
            if(perSet.insert(s).second == false) 
                return;
        }

        //2. 최소성 검사
        string s = ""; //문자열로 만들거라서 
        for(int i = 0; i < per.size(); i++){
            s+= to_string(per[i]);
        }

        for(int i = 0; i < uni.size(); i++){
            int num = 0; //s와 uni[i][j]의 값이 있다면 num++
            for(int j = 0 ; j < uni[i].size(); j++){
                if(s.find(uni[i][j]) != string::npos) 
                    num++; 
            }
            if(num == uni[i].size())
                return;
        }
        uni.push_back(s); //최소성에 만족하므로 uni에 넣어줌
        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) {
    // 유일성은 중복 없는것 (set이용)
    // 최소성은 그보다 속성이 작은 유일성만족 후보키가 없는것
    for(int i = 1; i <= relation[0].size(); i++){
        vector<int> p(i, 0);
        per = p;
        permutation(0, i, 0, relation); // 후보키 가능한 조합을 만든다.
    }
    return uni.size();
}

비트연산을 이용한 방법

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

// 조합 경우의 수
/*
     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) - 학번, 이름, 전공, 학년
     */

//최소성 확인
bool minimal(vector<int> &vec, int now)
{
    //ans에 있던 조합이 이번에 들어온 조합이랑 같은 것인지 확인
    for (int i = 0; i < vec.size(); i++)
        if ((vec[i] & now) == vec[i]) //같다면(&) 최소성 만족 X
            return false;
    return true;
}
int solution(vector<vector<string>> relation)
{
    int n = relation.size();           //ROWSIZE
    int m = relation[0].size();        //COLSIZE
    vector<int> ans;                   //후보키(유일성, 최소성 만족)
    for (int i = 1; i < (1 << m); i++) //i < (1 << m) : i가 1
    {
        set<string> s; //유일성 체크용 set
        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);
        }

        //유일성(s.size() == ROWSIZE)과 최소성(minimal) 체크
        if (s.size() == n && minimal(ans, i))
            ans.push_back(i);
    }
    return ans.size();
}

---

회고

너무너무 어려워서 아직 코테 문제를 풀어낼 역량이 부족한 것 같다는 생각이 든다 ....
알고리즘 공부도 부족한 것 같고, 새로 알게된 것들도 있었다 ....
또 풀어보아야지 ... ㅜㅜ