[프로그래머스 - C++] 후보키

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

코딩테스트 연습 - 후보키

 

풀이

저는 재귀함수를 이용해서 브루트포스 방식으로 각각의 조합을 직접 생성해서 문제를 해결하였습니다.

 

후보키 생성에 있어서는 크기가 1인 후보키부터 relation의 속성 값 수 크기까지 작은 개수로 이루어진 것 부터 생성합니다.

이때 재귀를 이용해서 string의 뒤에 새로운 인덱스를 추가하는 방식으로 구현해 주었습니다.

 

원하는 재귀를 통해 후보키 크기의 string을 생성한 경우 우선 유일성을 먼저 확인합니다. (check()함수)

유일성 확인에는 각각의 튜플이 후보키에 대해 갖는 값들을 string형태로 뒤에 연결해줍니다.

그런 뒤 set을 이용해서 이 string갑들 중 중복되는 값이 있는 지 확인합니다.

중복되는 값이 없는 경우엔 유일성이 만족되며, 있는 경우엔 유일성이 만족 되지 않습니다.

 

유일성이 만족되면, 최소성을 확인합니다.

새로 생성한 후보키 string을 now라고 할 때, 이 now를 이전에 생성된 후보키들이 모인 벡터인 added의 원소 string과 비교합니다.

now에 added의 원소인 각각의 string에대해 각 문자가 모두 포함되는지 확인하고, 모두 포함되는 경우가 존재한다면 유일성을 만족하지 못한것으로 판단합니다.

 

비트마스킹을 사용하시는 분들도 있던데 저는 그냥 제가 편한 방법으로 코드를 짰습니다!

 

 

그래서 그런지 코드가 꽤 기네요...ㅠㅠㅠ

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

using namespace std;
int answer = 0;
vector<string> added;

//유일성 확인 함수
bool check(string temp, vector<vector<string>> relation){
    vector<string> check;
    set<string> same;
    
    int tuple = relation.size();
    check.resize(tuple);
    
    //선택한 속성들을 가지고 각각의 튜플의 해당 속성 값을 string으로 연결
    for(int i=0; i<temp.length(); i++){
        for(int j=0; j<tuple; j++){
            check[j] += relation[j][temp[i]-'0'];
        }
    }
    //생성한 string중 중복값이 있는지 확인
    for(int i=0; i<tuple; i++){
        auto it = same.find(check[i]);
        if(it==same.end())
            same.insert(check[i]);
        //중복값 있는 경우 유일성 만족 X
        else
            return false;
    }
    return true;
}

void dfs(int idx, int cnt, int size, string now, vector<vector<string>> relation){
    //원하는 size길이의 속성 string생성 함.
    if(size == cnt){
        //유일성 만족하는 경우
        if(check(now, relation) == true){
            //최소성 확인 - 이미 added에 추가된 string들의 각 문자가 now에 포함되어 있는지 확인.
            for(int j=0; j<added.size(); j++){
                bool already = true;
                for(int i=0; i<added[j].size(); i++){
                    //문자 하나씩 포함 여부 확인
                    string str = added[j].substr(i, 1);
                    //added[j]의 string의 문자 중 now에 없는게 하나라도 있는 경우
                    if (now.find(str) == std::string::npos) {
                        already = false;
		                break;
	                }
                }
                //now가 이미 added에 포함된 string의 문자들을 원소로함 - 최소성 X
                if(already == true)
                    return ;
            }
            //유일성, 최소성 모두 만족
            added.push_back(now);
            answer++;
            return ;
        }
        
        //유일성 만족 X
        else{
            return ;
        }
    }
    //후보키 크기가 아직 작음
    else {
        int attribute = relation[0].size();
        for (int i=idx+1; i<attribute; i++){
            string temp = now+to_string(i);
            //재귀로 후보키 하나 더 추가
            dfs(i, cnt+1, size, temp, relation);
        }
    }
}

int solution(vector<vector<string>> relation) {
    
    int attribute = relation[0].size();
    //j 크기의 후보키를 i부터의 속성을 이용해 생성하게 하는 재귀.
    for (int j=1; j<=attribute; j++){
        for (int i=0; i<attribute; i++){
            string temp = ""+to_string(i);
            dfs(i, 1, j, temp, relation);
        }
    }
    return answer;
}