프로그래머스 문제 - 후보키

프로그래머스 후보키 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

주어진 데이터베이스가 있습니다.
관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.
유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.
이때 후보 키의 최대 개수를 구해야합니다.

문제 풀이

이 문제에서 중요한 요점은 유일성이 지켜진 후보 키들 중 최소성을 가진 후보 키의 최대 갯수를 구하는것입니다.
데이터베이스의 가로줄을 나타내는 column과 세로줄을 나타내는 row값이 주어집니다.
각 row가 유일한 값을 가지고 있을 때 유일성이 지켜진 후보 키가 됩니다.
여기서 갯수를 기준으로 오름차순 정렬시켜 저장해둔 queue를 가지고 맨 위의 배열v를 가지고 나머지 배열이 부분집합이 되는지 확인해주며 answer값에 +1 시켜줍니다.
부분집합인 배열은 제외시켜고 queue내의 모든 배열을 확인시키는 동안 더해준 answer값이 후보 키의 최대 갯수가 됩니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<string>> relation) {
    int answer = 0;
    int columnSize = relation[0].size();
    int rowSize = relation.size();
    
    queue<vector<int>> keys;
    
    //검색을 위한 모든 경우의 수 계산
    vector<int> permutationArray(columnSize, 1);
    for(int num = 0; num < columnSize; num++)
    {
        permutationArray[num] = 0;
        vector<int> column_vec = permutationArray;
        vector<int> key;
        
        bool isNotKey;      
        do{
            isNotKey = false;
            key = vector<int>();
            
            //후보 키 생성
            for(int i = 0; i < column_vec.size(); i++)
            {
                if(column_vec[i] == 0)
                    key.push_back(i);
            }
            if(isNotKey)
                continue;
            
            for(int target = 0; target < key.size(); target++)
            {
                if(isNotKey)    break;
                for(int i = 0; i < rowSize; i++)
                {
                    if(isNotKey)    break;
                    for(int j = i+1; j < rowSize; j++)
                    {
                        if(isNotKey)    break;
                        //만약 튜플이 같을 경우 나머지 속성에서 판별 가능한지 확인
                        if(relation[i][key[target]].compare(relation[j][key[target]]) == 0)
                        {
                            bool temp = false;
                            for(int k = 0; k < key.size(); k++)
                            {
                                if(relation[i][key[k]].compare(relation[j][key[k]]) != 0)
                                {
                                    temp = true;
                                    break;
                                }
                            }
                            if(!temp)
                            {
                                isNotKey = true;
                            }
                        }
                    }
                }
            }
            
            if(!isNotKey)
            {                
                keys.push(key);
            }
            
            
        } while(next_permutation(column_vec.begin(), column_vec.end()));
    }
    
    //최소성 검사
    vector<int> currentVec;   
    while(!keys.empty())
    {
        vector<int> v;
        currentVec = keys.front();    keys.pop();
        int qSize = keys.size();
        for(int i = 0; i < qSize; i++)
        {
            v = keys.front(); keys.pop();
            //부분집합인지 체크
            if(!includes(v.begin(), v.end(), currentVec.begin(), currentVec.end()))
            {
                keys.push(v);
            }
        }
        answer++;
    }
    
    return answer;
}

출저

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