[Programmers] 후보키

안녕하세요. 이번 포스팅에서는 Programmers 후보 키 문제를 풀어보도록 하겠습니다.

 

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

코딩테스트 연습 - 후보키

 

위 링크에서 문제를 확인하실 수 있습니다. 

 

이 문제는 2019 KAKAO BLIND 채용 기출 문제이며, 그나마 쉬운 편인데 그래도 어렵습니다...

 

일단 문제를 보시면, 유일한 후보키를 모두 찾아야 하는 문제입니다. 따라서 만들 수 있는 모든 경우의 수를 우선 만들어야 합니다.

 

제가 요새 카카오 기출 문제를 자주 푸는데, 카카오 기출에서 이런 식으로 모든 경우의 수를 찾는 문제가 많이 나오는 것 같습니다.

 

경우의 수를 찾는 방법은 크게 DFS로 재귀적으로 depth를 확인하며 구하는 방법이 있고, next_permutation으로 구하는 방법이 있는데, 보통 전자가 직관적으로 이해가 쉽다는 장점이 있는 반면, 후자는 상대적으로 효율적입니다. 

 

저는 이 문제를 next_permutation을 활용하여 모든 경우의 수를 구해주었습니다.

 

이제 문제는 어떻게 최소성을 보장하냐의 문제인데, 제가 처음에 잘못 생각했던 부분이, 

 

만약에 결과에 {2, 3}과 {1, 3, 4}가 있다면 {2, 3}은 {1, 3, 4}의 부분집합이 아니기 때문에 둘 다 결과에 추가되어야 하는데, 저는 {2, 3}이 결과에 추가된 순간 2와 3 모두 방문 배열 처리하여 {1, 3, 4}가 카운트되지 않는 현상이 있었습니다.

 

따라서 이 문제는 일일이 이전에 포함된 집합과 현재 비교하는 집합의 포함관계를 판단하여 결과에 추가할 지 말 지 결정해야 합니다. 

 

<소스 코드>

#include <bits/stdc++.h>
using namespace std;

bool resultContains(vector<set<int>>& resultSet, set<int> ret) {
    for(int i = 0; i < resultSet.size(); i++) {
        set<int> cur = resultSet[i];
        int count = 0;
        for(auto a : cur) {
            if(ret.find(a) != ret.end()) count++; 
        }
        if(count == cur.size()) return true;
    }
    return false;
}
int solution(vector<vector<string>> relation) {
    int answer = 0;
    int n = relation[0].size();
    vector<set<int>> resultSet;
    for(int _size = 1; _size <= n; _size++) {
        vector<bool> comb(n, 1);
        for(int i = 0; i < n - _size; i++) comb[i] = 0;

        do {
            vector<int> checkCol;
            for(int i = 0; i < comb.size(); i++) if(comb[i]) checkCol.push_back(i);

            set<string> s;
            for(int i = 0; i < relation.size(); i++) {
                string next = "";
                for(int j = 0; j < checkCol.size(); j++) {
                    next += relation[i][checkCol[j]];
                }
                s.insert(next);
            }

            if(s.size() == relation.size()) {
                set<int> ret;
                for(int i = 0; i < checkCol.size(); i++) ret.insert(checkCol[i]);
                if(resultContains(resultSet, ret)) continue;
                resultSet.push_back(ret);
                answer++;
            }
        }while(next_permutation(comb.begin(), comb.end()));
    }
    return answer;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.