[ 프로그래머스 후보키 (Lv2) ] (C++)

프로그래머스의 후보키(Lv2) 문제이다.

 

[ 문제풀이 ]

주어진 데이트베이서에서 후보키의 갯수를 구해야 하는 문제이다.

 

#1. 조합 구현하기

본인이 가장 먼저 진행했던 과정은 조합을 구현하는 과정이었다.

조합이 어디에 사용되는지 부터 이야기를 해보자.

우리는 주어진 Attribute들 중에서 유일성과 최소성을 가진 후보키를 구해야 한다. 이 때, 후보키는 하나가 될 수도 있고, 여러개의 조합으로 이루어질 수도 있다.

문제에서 설명으로 주어진 부분을 보면, "학번"은 "학번"이라는 Attribute 하나만으로도 후보키가 될 수 있지만, [ "이름", "전공" ] 같은 경우에는 2개의 Attribute의 조합으로 이루어져 있는 후보키가 된다.

 

따라서, 우리는 주어진 속성들의 조합을 통해서 후보키를 찾아볼 것이다.

순열이 아닌 조합인 이유는 다음과 같다. 후보키로 [ "이름" , "전공" ] 을 찾았다고 가정했을 때, [ "전공" , "이름" ] 또한 후보키가 될 수 있는 것은 아니다. 즉 ! 주어진 순서에 상관없이 결과가 같기 때문에 순열이 아닌 조합을 이용해서 구현하였다.아직 조합에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ 조합 알아보기 (Click) ]

 

그렇다면 우리는 주어진 속성들 중에서 몇 개를 선택해서 후보키를 찾아봐야할까 ???

후보키는 속성 1개만으로도 될 수 있지만, 주어진 속성을 모두 사용해야만 후보키가 가능한 경우도 존재한다.

즉 ! 1개를 뽑는 과정부터 모든 속성들을 다 뽑는 과정까지 모두 진행을 해주어야 한다.

본인이 구현한 1개부터 모든 속성들을 다 뽑는 과정을 조합으로 구현한 코드는 다음과 같다.

int Answer, Attribute_Size;
vector<bool> Select;
vector<int> V;
vector<vector<string>> Relation;

void DFS(int Idx, int Cnt, int Total_Cnt)
{
	if (Cnt == Total_Cnt)
	{
		if (Check() == true) Answer++;
		return;
	}

	for (int i = Idx; i < Attribute_Size; i++)
	{
		if (Select[i] == true) continue;
		Select[i] = true;
		V.push_back(i);
		DFS(i, Cnt + 1, Total_Cnt);
		V.pop_back();
		Select[i] = false;
	}
}

void Make_Combination()
{
	for (int i = 1; i <= Relation[0].size(); i++)
	{
		DFS(0, 0, i);
	}
}

 

#2. 유일성

이제 후보키를 판단하기 위해서 #1의 과정에서 뽑은 속성들의 조합이 유일성을 만족하는지 판단하는 과정에 대해서 진행을 해보자. 유일성이라는 것은 모든 튜플에 대해서 유일하게 식별되어야 한다는 것을 의미한다.

본인은 이를 "문자열"로 속성들을 이어 붙인뒤에 판단해 주었다.

예를 하나 들어보자.

[ "a", "b", "c" ] , [ "a", "b", "d" ] , [ "a", "b", "e" ]

위와 같은 경우가 주어졌을 때, 3개의 속성을 모두 가지는 경우가 후보키의 유일성을 만족하는지 판단해보자.

가장 앞에서부터 0번속성, 1번속성, 2번속성이라고 번호 붙였을 때, [ 0번 , 1번 , 2번 ] 이 후보키의 유일성을 만족하는지 확인하는 과정인 것이다.

이를 문자열로 모두 이어붙여보자.

첫 번째 데이터의 경우 0번, 1번, 2번을 모두 이어붙여서 문자열을 만들게되면 "abc"가 되고,

두 번째 데이터의 경우 "abd"

세 번째 데이터의 경우 "abe"가 된다.

3개의 데이터가 모두 동일한 결과를 가지지 않고 서로 다른 결과를 가지기 때문에 이를 유일성을 만족한다고 볼 수 있다. 하지만 반대로, [ 0번 , 1번 ] 의 조합으로 이루어진 후보키가 유일성을 만족하는지 확인해보면...

첫 번째 데이터 = "ab"

두 번째 데이터 = "ab"

세 번째 데이터 = "ab" 로 동일한 결과를 가지는 경우가 발생한다. 따라서, 이 경우에는 유일성을 만족한다고 볼 수 없다.

본인은 이런식으로 문자열로 모두 이어붙인 후에 Vector를 통해서 유일성을 판단해 주었다.

bool Check_Uniqueness()
{
	vector<string> Temp;
	for (int i = 0; i < Relation.size(); i++)
	{
		string Result = "";
		for (int k = 0; k < V.size(); k++)
		{
			int Idx = V[k];
			Result += Relation[i][Idx];
		}

		if (find(Temp.begin(), Temp.end(), Result) != Temp.end()) return false;
		else Temp.push_back(Result);
	}

	return true;
}

위의 코드에서 안쪽에 있는 내부 for문에 있는 Vector 'V'가 "현재까지 내가 뽑은 속성들의 조합" 이 저장되어 있는 Vector이다.

Result 라는 string형 변수에 속성들이 가지는 값을 문자열의 형태로 모두 이어붙여서 하나의 문자열을 만들어 주었다. Temp 라는 Vector는 "기존에 발생한 문자열들을 저장" 해주기 위한 Vector이다.

결과적으로, 만약 Temp에서 생성된 문자열을 찾았다면, 이는 기존에 한번 나왔던 문자열이라는 것을 의미하고, 이는 유일성을 만족하지 않는다고 판단할 수 있다.

 

#3. 최소성

이번에는 최소성을 판단하는 방법에 대해서 이야기를 해보자.

먼저, 최소성을 판단하기 위해서는 "기존에 선정된 후보키의 리스트" 가 필요하다.

예를 들어서, 현재 내가 [ 0번, 1번, 2번 ] 속성들의 조합으로 후보키가 될 수 있는지 판단을 하고 있을 때, 만약 기존에 [ 0번, 1번 ] 의 조합으로만 후보키가 된다면 이는 적절한 후보키가 아니게 된다.

즉 ! 기존에 만들어놓은 후보키들의 리스트가 필요하다.

 

그렇다면 한 가지 예를 통해서 알아보자.

기존에 선정된 후보키 = [ 0 , 1 ] , [ 0 , 2 ] , [ 1 , 2 ]

현재 후보키로 판단하려는 속성의 조합 = [ 1 , 2 , 3 ] , [ 1 , 3 , 4 ]

위와 같은 상황을 생각해보자.

위의 숫자들은 간단하게 이야기해서, "속성들의 번호" 를 의미하는 것이다.

[ 0 , 1 ] = 0번 속성과 1번 속성의 조합으로 이루어진 후보키는 유일성과 최소성을 모두 만족하는 후보키입니다.

라는 것을 의미한다.

이 상황에서 [ 1 , 2 , 3 ] 이 최소성을 만족하는지 생각을 해보자.

[ 0 , 1 ] 과 [ 1 , 2 , 3 ] 을 비교했을 때에는, 최소성을 만족한다고 볼 수 있다.

왜냐하면 [ 1 , 2 , 3 ] 중에서 어떤 속성 하나를 뺀다고 하더라도 후보키가 될 수 없기 때문이다.

[ 0 , 2 ] 와 [ 1 , 2 , 3 ] 또한 마찬가지이다.

[ 1 , 2 ] 와 [ 1 , 2 , 3 ] 을 비교해보자. 이 때는, 비교를 해보면 속성 '3'을 뺀다고 하더라도 후보키가 될 수 있다.

즉 ! 이는 최소성을 만족하지 않으므로 후보키가 될 수 없다는 것을 의미한다.

 

반면, [ 1 , 3 , 4 ] 같은 경우에는 기존에 존재하는 모든 후보키들과 비교를 해 보아도, 어느 속성 하나를 뺀다고 하더라도 후보키가 되지 않기 때문에 최소성을 만족한다고 할 수 있다.

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int Answer, Attribute_Size;
vector<bool> Select;
vector<int> V;
vector<vector<int>> Candidate;
vector<vector<string>> Relation;
 
void Make_Attribute()
{
    Select.resize(Relation[0].size(), false);
    Attribute_Size = Relation[0].size();
}
 
bool Check_Uniqueness()
{
    vector<string> Temp;
    for (int i = 0; i < Relation.size(); i++)
    {
        string Result = "";
        for (int k = 0; k < V.size(); k++)
        {
            int Idx = V[k];
            Result += Relation[i][Idx];
        }
 
        if (find(Temp.begin(), Temp.end(), Result) != Temp.end()) return false;
        else Temp.push_back(Result);
    }
 
    return true;
}
 
bool Check_Minimality()
{
    if (V.size() == 1) return true;
 
    // V에는 후보키로 사용할 Attribute들의 조합이 들어있다.
    // "12"가 후보키일떄, "012"가 삽입되면 ?
    // "12"가 후보키일떄, "134"가 삽입되면 ?
    // "01"이 후보키일때, "134"가 삽입되면 ?
    for (int i = 0; i < Candidate.size(); i++)
    {
        bool Flag = false;
        for (int j = 0; j < Candidate[i].size(); j++)
        {
            int Key = Candidate[i][j];
            if (find(V.begin(), V.end(), Key) == V.end())
            {
                Flag = true;
                break;
            }
        }
        if (Flag == false) return false;
    }
    return true;
}
 
bool Check()
{
    if (Check_Uniqueness() == true && Check_Minimality() == true)
    {
        Candidate.push_back(V);
        return true;
    }
    return false;
}
 
void DFS(int Idx, int Cnt, int Total_Cnt)
{
    if (Cnt == Total_Cnt)
    {
        if (Check() == true) Answer++;
        return;
    }
 
    for (int i = Idx; i < Attribute_Size; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        V.push_back(i);
        DFS(i, Cnt + 1, Total_Cnt);
        V.pop_back();
        Select[i] = false;
    }
}
 
void Make_Combination()
{
    for (int i = 1; i <= Relation[0].size(); i++)
    {
        DFS(0, 0, i);
    }
}
 
int solution(vector<vector<string>> relation)
{
    Relation = relation;
    Make_Attribute();
    Make_Combination();
    return Answer;
}