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

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

처음 이 문제를 봤을 때, 후보키가 될 수 있는 키들을 선정하려면 어떻게 해야할까 고민을 많이 했다.

이미 후보키가 된 조합이 포함되어 있다면 후보키가 될 수 없으므로 이를 구현하면 되지 않을까? 고민을 했다.

 

처음에는 재귀 함수를 만들어 가지치기를 하려고 했는데 잘 안돼서 그냥 키 하나로 만들 수 있는 경우, 키 2개로 만들 수 있는 경우... 의 모든 조합을 구하고, 이미 적은 키로 만들어진 경우는 제외하도록 코드를 구현했다. 

 

나중에 다시 생각해보니 키들의 조합을 만드는 부분을 재귀함수로 가지치기 할 수 있을 것 같아서 재귀함수로 문제를 다시 풀었다.

 

예를 들어 1번 키를 무조건 포함, 2번 키를 무조건 포함(1번 키는 포함x), 3번 키를 무조건 포함(1, 2번 키는 포함x) 와 같은 식으로 탐색을 한다.

 

이렇게 하면 1번 키로 후보키를 만들 수 있다면 1번키를 포함한 경우를 제외할 수 있다.

 

하지만 실제로 이렇게 코드를 구현하면, 문제점이 하나 생긴다.

순차적으로 조합을 만들었기 때문에 (2, 3)키가 후보가 될 수 있다고 판단 했는데, 3번 키로만 후보키를 만들 수 있는 경우가 생길 수 있다.

 

그렇기 때문에 3번 키로만 후보키를 만드는 경우가 생기면 3번 키를 포함한 경우들이 있는지 찾아서 제외해 주는 부분을 구현하면 된다.

 

ex) 만약 4, 5번 키로 후보를 만들 수 있다면, (1, 2, 4, 5)키로 후보키를 만드는 경우를 제외한다.

 

이제 후보키의 조합을 구하는 방법을 알아봤으니 후보키가 되는지 어떻게 판단할 지 생각해 보자.

 

가장 쉬운 방법은 set을 이용하는 것이다.

후보키들이 선정됐으면, 인원마다 후보키를 이용해 튜플을 만든다.

 

그리고 튜플을 전부 set에 넣으면 중복된 경우는 사라진다.

 

그러므로 인원수와 set에 있는 튜플의 수가 같다면 후보키가 되는 것이고, 수가 다르다면 중복이 있다는 뜻이므로 후보키가 될 수 없다.

 

이를 이용해 모든 후보키들의 경우의 수를 구하고 개수를 return하면 된다.

 

 

​

[아이디어 정리]

1. 재귀함수를 만들어 후보키가 만들어지는 경우는 그 하위의 조합을 탐색하지 않도록 코드를 구현한다.
2. 예외가 존재할 수 있으므로 후보키를 만들 수 있는 경우 하위 조합이 set에 포함되어 있는지 검사하고, 만약 포함되어 있다면, 제외해 준다.
3. 최종적으로 후보키 set의 개수를 return 한다.

 

 

 

Code

 

 

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

int answer=0;
void MakeKey(int stIdx,vector<vector<string>> &relation, vector<bool> keyCombi, set<vector<bool>> &sss)
{
    keyCombi[stIdx]=true;
    set<vector<string>> CheckS;
    for (int i=0; i<relation.size(); i++)
    { // 현재 후보키들 조합으로 튜플을 만들어 개수 세기
        vector<string> nV(relation[0].size(),"!");
        for (int j=0; j<relation[0].size(); j++)
        {
            if (keyCombi[j])
            {
                nV[j]=relation[i][j];
            }
        }
        CheckS.insert(nV); // 튜플을 삽입
    }
    set<vector<bool>>ns;
    if (CheckS.size()==relation.size())
    { // 만약 후보키가 된다면 set에 삽입하고 탐색 종료
        vector<bool> nnv;
        for (set<vector<bool>>::iterator it=sss.begin(); it!=sss.end(); it++)
        { // 이 키를 포함한 조합이 후보키 set에 있는지 탐색해 없애주는 부분
            nnv=*it;
            int cnt=0, checkCnt=0;
            for (int i=0; i<nnv.size(); i++)
            {
                if (keyCombi[i])
                {
                    cnt+=1;
                    if (nnv[i])
                    {
                        checkCnt+=1;
                    }
                }
            }
            if (cnt!=checkCnt)
            {
                ns.insert(nnv);
            }
        }
        ns.insert(keyCombi);
        sss=ns;
        return;
    }    
    for (int i=stIdx+1; i<relation[0].size(); i++)
    { // 만약 이 키로 후보키를 못 만든다면, 하위 조합을 더 탐색해본다. 
        MakeKey(i, relation, keyCombi,sss);
    }
}

int solution(vector<vector<string>> relation) {
    int maxKeyCnt=relation[0].size();
    set<vector<bool>> sss;
    for (int i=0; i< maxKeyCnt; i++)
    {
        MakeKey(i, relation, vector<bool>(maxKeyCnt,false),sss);
    }
    return sss.size();
}

 

---

처음에 조합을 만드는 부분에서 고민이 많이 됐다.

bit연산으로 조합을 해결하는 방법도 있지만, bit연산을 많이 사용해보지 않아서 직접 조합을 만들도록 코드를 구현했었는데, 정말 코드가 길어졌다.

하위집합에 있는지 판단하는 부분을 and연산으로 계산하면 되는데... 나중에 bit연산을 사용해보며 익숙해지자

프로그래머스