프로그래머스 Level 2 후보키

후보키 (프로그래머스 Level 2)

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

생각보다 많이 어려웠다
처음에는 막연히 set을 사용하는 것은 알았으나
풀다 보니, ‘모든 조합’에 관한 확인이 필요하다는 것을 알고
백트래킹을 시도하였다

그러나 여러 개의 ‘속성’으로 ‘후보키’를 찾는 경우에 대하여 명확한 해답이 보이지 않았다
(1,2,3 등 3개 이상의 속성에 대한 ‘유일성’ 확인 방식에 대한 고민)

이후 곰곰히 생각해보니
string 타입이기에 ‘중복’ 여부를 ‘문자열’들을 ‘더하여’ 체크할 수 있다는 점을 깨달았고
코드를 수정하여 통과하였다

구체적인 로직은
크게 2가지로

1. 유일성 확인 : 주어진 조합에 관하여 해당 조합들을 더하여 문자열을 만들었을때
   중복되지 않는다면 ‘유일’하다고 판단한다
   ex) 학번이라는 Column에 대하여 100,200,300 이 들어있다면
   각각의 문자열은 중복되지 않으므로 후보키로 인식
   

2. 최소성 확인 : 주어진 속성들에 대하여 이미 유일성이 보장된 속성이 들어있다면 해당 조합은 걸러준다
   ex) 1,2,3 이라는 조합으로 ‘유일성’을 확인했으나, 이미 2,3 이라는 조합의 유일성이 검증된 경우
   해당 조합은 최소성 조건을 만족하지 못한다
   

set 자료구조를 사용하여 최소성을 확인하고
백트래킹을 이용하여 모든 조합의 수를 시도하였다
그리고 string을 더하는 방식으로 유일성을 체크하였다

풀고 보니 중간에 너무 복잡하게 생각했단걸 다시 알게 되었다
level 2 문제이지만, 실제로 코드테스트에서 이 문제를 보았을 때,
시간 내로 풀 수 있을거란 자신이 없다

조금 더 많은 문제를 풀어봐야 할 것 같다

Code

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

using namespace std;

bool hasAllElements(const set<int>& setA, const set<int>& setB) 
{
    for (const int& elem : setA) 
    {
        if (setB.count(elem) == 0) 
        {
            return false;
        }
    }
    return true;
}

void dfs(set<int>& uSet,int nowIdx, set<set<int>>& candiKeys,int count,const vector<vector<string>>& relation)
{
    int rSize = relation.size();
    int vSize = relation[0].size();

    uSet.insert(nowIdx);
    if (candiKeys.find(uSet) != candiKeys.end() ||
        uSet.size() > count)
    {
        uSet.erase(nowIdx);
        return;
    }

    if (uSet.size() == count)
    {
        bool isCheck = true;
        set<string> ss;

        for (int i = 0; i < rSize; i++)
        {
            string temp = "";
            for (int uV : uSet)
            {
                temp += relation[i][uV];
            }

            if (ss.find(temp) != ss.end())
            {
                isCheck = false;
                break;
            }

            ss.insert(temp);
        }

        if (isCheck)
        {
            bool isInCheck = false;
            for (const set<int>& candi : candiKeys)
            {
                if (hasAllElements(candi, uSet) ||
                    hasAllElements(uSet, candi))
                {
                    isInCheck = true;
                    break;
                }
            }

            if(isInCheck == false)
                candiKeys.insert(uSet);
        }

    }

    for (int i = nowIdx + 1; i < vSize; i++)
    {
        dfs(uSet, i, candiKeys, count, relation);
    }

    uSet.erase(nowIdx);
}

int solution(vector<vector<string>> relation) {
    int rSize = relation.size();
    int vSize = relation[0].size();

    set<set<int>> candiKeys;

    int count = 1;
    while (count <= vSize)
    {
        for (int i = 0; i < vSize; i++)
        {
            set<int> uSet;
            dfs(uSet,  i, candiKeys, count,relation);
        }

        count++;
    }
    
    return candiKeys.size();
}