[프로그래머스 2019 KAKAO BLIND RECRUITMENT] (level2) 후보키

 

회고

1. 그냥 같은 row끼리 Concat하면 되는데 Join을 해버렸다. 정신이 어떻게 된것 같다.

• 그래서 미친듯이 많은 재귀를 돌리고 메모리가 터졌다..

2. 비트셋을 이용해 본것은 처음 

3. vector<vector<int>> 내 원소들간 중복제거를 연구해봐야 겠다.

4. 프로그래머스에 전역 변수 선언을 하는것도 한번 참고해 보자.

5. 이상한 반례 : 다음 테이블의 후보키는 전부 가능한거 아닌가? 

• 근데 막상 풀었을때, 후보키는 1개 밖에 사용 못했다.

학번	이름	전공	학년
"100"	"ryan"	"music"	"2"

 

#include <bits/stdc++.h>

using namespace std;

vector<int> CandiKey;
int ColNum = -1;
int RowNum = -1;

int solution(vector<vector<string>> relation) {
    int answer = 0;
    ColNum = relation[0].size();
    RowNum = relation.size();
    
    for(int i =0; i < (1 << ColNum); i++) {
        unordered_set<string> s; 
        bool flag = true;
        for(int k = 0; k < RowNum; k++) {
            string tmp = "";
             for(int j = 0 ; j < ColNum; j++) {
                if( (i & (1 << j)) != 0) {
                    tmp += relation[k][j];
                }
            }
            if(s.find(tmp) != s.end()) { flag = false; break; }
            s.insert(tmp);
        }
        if(flag == true) {
            bool uniqueFlag = true;
            for(auto& ck : CandiKey) {
                if((i & ck) == ck) {
                    uniqueFlag = false;
                    break;
                }
            }
            if(uniqueFlag) CandiKey.push_back(i);
        }
    }
    
    
    // for(const auto& ck : CandiKey) {cout << bitset<8>(ck).to_string() << ' ';} cout << endl;
    return CandiKey.size();
}