[프로그래머스] 후보키

---

🔗 문제 링크

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

프로그래머스

---

반응형

728x90

👩‍💻 코드

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

using namespace std;

bool isUnique(const vector<vector<string>> &relation, int subset){
    set<string> unique;
    
    for (const auto& row : relation){
        string key;
        
        for (int col = 0; col < relation[0].size(); col++){
            if(subset & (1 << col)){
                key += row[col];
            }
        }
        
        if (unique.find(key) != unique.end()){
            return false;
        }
        
        unique.insert(key);
    }
    
    return true;
}

bool isMinimal(const vector<int> &candidateKeys, int subset){
    for (int key : candidateKeys){
        if ((key & subset) == key){
            return false;
        }
    }
    
    return true;
}

int solution(vector<vector<string>> relation) {
    int column = relation[0].size();
    vector<int> candidateKeys;
    
    for (int i = 1; i < (1 << column); i++) {
        if (isUnique(relation, i) && isMinimal(candidateKeys, i)){
            candidateKeys.push_back(i);
        }
    }
    
    return candidateKeys.size();
}

---

📝 풀이

후보키가 가능한 컬럼의 모든 조합을 비트 마스크를 사용하여 탐색합니다.

각 조합의 후보키들의 유일성과 최소성을 판단하여 둘 다 만족할 경우에만 후보키로 추가합니다.

 

유일성을 확인하는 함수 isUnique는 릴레이션의 각 행을 순회하며 각 튜플에 선택된 속성을 결합하여 key로 만듭니다.

결합하여 만든 key값을 set에 저장하고 만약 중복된 키가 있다면 false를 return 합니다.

중복된 키 값이 없어 반복문이 종료되면 유일성을 만족하여 true를 return 합니다.

 

최소성을 확인하는 함수 isMinimal은 현재 subset이 기존 후보키의 부분집합인지 확인합니다.

부분집합인 경우 false를 아닌 경우 true를 return 합니다.

 

최종적으로 후보키의 개수 candidateKeys.size()를 return 합니다.