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

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

프로그래머스

<풀이>

1. 가능한 모든 후보키를 계산합니다.

2. 유일성과 최소성을 확인하여 가능한 후보키만을 결과값으로 저장합니다.

3. 결과를 출력합니다.

 

<해법>

1. 가능한 모든 후보키를 계산하는 방법.

=> 모든 경우의 수를 계산하는 대표적인 방법으로 '백트래킹'이 있습니다. 저는 '백트래킹'을 재귀함수를 이용하여 구현하였고, 저는 구현하기 이전에 아래와 같은 그림으로 큰 틀을  잡습니다.

 

2. 유일성 확인하는 방법

=> 해당하는 속성의 값을 한 문자열로 만들고 정렬을 해준 후, 같은 문자가 있는지 확인하였습니다. 같은 문자가 있을 경우 유일성 조건에서 탈락하는 방식으로 진행하였습니다.

 

3. 최소성 확인하는 방법

=> 확인해야 할 후보키를 정답이 가능한 후보키들과 비교하였습니다. 정답이 가능한 후보키에 부분집합만 되지 않으면 가능하므로, 다른 속성이 한가지라도 있는지 확인하고 한가지라도 있으면 최소성 조건에 부합하는 방식으로 진행하였습니다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int col, row;
vector<vector<string>> r;
vector<int> v;
vector<vector<int>> key;
 
void go(int index, int cnt) {
 
    //원하는 개수를 다 뽑았으면
    if (cnt == 0) {
        
        //최소성 확인 - 후보키에 이미 같은 조합이 있는지 확인
        if (!key.empty()) {
            for (int i = 0; i < key.size(); i++) {
 
                bool isMinimal = false;
 
                //후보키 안에 모두 같은 속성이 있을 시 minimal X
                //-> 후보키 안에 하나라도 다른 속성이 있으면 OK
                for (int j = 0; j < key[i].size(); j++) {
                    bool alreadyIn = false;
                    for (int k = 0; k < v.size(); k++) {
                        if (key[i][j] == v[k]) {
                            alreadyIn = true;
                        }
                    }
                    if (!alreadyIn) {
                        isMinimal = true;
                    }
                }
                
                if (!isMinimal) {
                    return;
                }
            }
        }
        
        //유일성 확인 - 모든 튜플을 식별할 수 있는지 확인
        vector<string> cmp;
        bool isUnique = true;
 
        //후보키로 문자열 만들기
        for (int i = 0; i < row; i++) {
            string s = "";
            for (int j = 0; j < v.size(); j++) {
                s += r[i][v[j]];
            }
            cmp.push_back(s);
        }
 
        sort(cmp.begin(), cmp.end());
        
        //문자열 중 같은 것이 있다면 -> 식별X
        for (int i = 0; i < row - 1; i++) {
            if (cmp[i] == cmp[i + 1]) {
                isUnique = false;
            }
        }
 
        //최종적으로 가능한 후보키 저장
        if (isUnique) {
            key.push_back(v);
        }
 
        return;
    }
 
    //갯수만큼 저장
    for (int i = index; i < col; i++) {
        v.push_back(i);
        go(i + 1, cnt - 1);
        v.pop_back();
    }
 
    return;
}
 
int solution(vector<vector<string>> relation) {
    int answer = 0;
 
    //전역변수에 값 저장
    r = relation;
    col = relation[0].size();
    row = relation.size();
 
    //1,2.. 개씩 뽑기
    for (int i = 1; i <= col; i++) {
        go(0, i);
    }
 
    //결과 저장
    answer = key.size();
 
    return answer;
}

 

백트래킹에 대해 알아볼 수 있는 문제였습니다.