프로그래머스[programmers] - 후보키(C++)[LV2]

📕문제

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

프로그래머스

---

🔎문제 풀이

해당 문제를 풀 기전에 유일성과 최소성을 설명하고자 합니다.

---

💡유일성?

릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.

위 테이블에서 칼람을 유일하게 식별할 수 있다면, 그 칼럼은 유일성이 있다고 합니다.

학번을 보면 모든 값들이 다 다른 것을 알 수 있습니다.

따라서 해당 테이블에서 학번을 통해서 유일하게 식별할 수 있습니다.

이러한 칼럼 학번은 유일성을 만족한다고 볼 수 있습니다.

 

이름을 보시면 apeach가 2명입니다.

따라서 이름만 보면 테이블을 식별할 수 없기 때문에 해당 칼럼은 유일성을 만족하지 않습니다.

 

유일성은 단일칼럼이 아니라, 묶어서 검사할 수 있습니다.

예를 들어서 {이름,전공}을 하나의 칼럼으로 묶으면 테이블을 식별할 수 있기 때문에

{이름, 전공}은 유일성을 만족한다고 볼 수 있습니다.

---

💡최소성?

유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다

최소성에서 말하고자 하는 바는 유일하게 식별하는데 꼭  필요한 속성들로만 구성되어야 한다입니다.

위에서 학번, {이름, 전공}은 유일성을 만족한다고 설명했습니다.

 

그렇다면 {학번, 이름, 전공}도 유일성을 만족하지 않을까??라는 의문이 생길 것입니다.

물론 유일성은 만족합니다. 하지만 {학번}만으로도 유일성을 만족하기 때문에 {학번, 이름, 전공}은 최소성을 만족하지 않습니다.

이렇게 유일성을 만족하는 칼럼들의 집합은 반드시 필요한 속성들로만 구성되어야 한다가 최소성의 의미입니다.

---

🔎풀이 방식

각 칼럼들을 1개, 2개, 3개, n 개씩 묶어서 유일성을 판단하는지 확인해야 합니다.

저는 조합을 사용해서 원소가 1개일 때, 2개일 때, 3개일 때의 경우의 수를 구해서 유일성을 먼저 판단했습니다.

 

C++에서 조합은 next_permutation을 통해서 구현할 수 있습니다.

https://twpower.github.io/90-combination-by-using-next_permutation

[Algorithm] C++에서 next_permutation을 이용해 조합(Combination) 구하기

next_permutation에 대한 자세한 내용은 위 블로그를 통해서 확인하시면 될 거 같습니다.

 

유일성에 대한 판별은 해당 칼럼의 원소들 중 같은 원소가 있는지를 검사합니다.

저는 map을 통해서 원소를 넣다가, 만약 중복되는 원소가 있다면 유일성을 만족하지 않는다고 처리를 하고 중단시켰습니다.

만약 2개 이상의 칼럼을 판단할 때는 간단하게 2개의 칼럼을 더한 문자열로 비교처리를 해줬습니다.

(단순하게 이렇게 처리해도 다 식별이 가능합니다)

 

다음은 최소성 판별입니다.

위에서 유일성을 만족한 칼럼들을 문자열로 더해서, 이 문자열들이 유일성을 만족했는지 안 했는지 검사를 해야 합니다.

예를 들어 {1}이 유일성을 만족할 경우 {1,2}가 유일성을 만족해도 이미 {1}이 유일성을 만족했기 때문에

{1,2}는 최소성을 만족하지 못합니다.

 

아마 해당 문제를 푸셨던 대부분의 사람들이 최소성을 판별하는 부분에서 막혔을 거라고 생각합니다.

(저도 최소성에서 굉장히 시간을 많이 썼습니다)

 

우선 저는 문자열로 칼럼들을 기록해서, 단순하게 find만 사용해서 비교했었습니다.

이 방법의 문제점은 만약 {1,2}가 유일성을 만족할 경우 {1,3,2}에 대한 최소성을 검사할 수가 없었습니다.

왜냐하면 {1,3,2}에는 {1,2}라는 단순한 문자열을 비교했기 때문입니다.

따라서 조합을 구할 때, 순서를 통일하던가, 아니면 원소 하나하나를 비교해서 찾아야 합니다.

 

자세한 구현 내용은 전체 코드와 주석을 통해서 설명하겠습니다.

---

💻코드

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

vector<string>p;
int row,col=0;
int funct(vector<vector<string>> relation,vector<int>num){
    map<string,int>m;
    for(int i=0; i<row;i++){
        string temp="";
        for(int j=0; j<num.size();j++)
            temp+=relation[i][num[j]];
        if(m.find(temp)!=m.end())//만약 이미 map에 동일한 값이 있다면 유일성을 만족 못함.
            return 0; //0을 리턴.
        m.insert(make_pair(temp,0)); //map에 동일 값이 없다면 추가.
    }
    string r=""; 
    for(int i=0; i<num.size();i++)
        r+=to_string(num[i]);//r은 이번 실행에서 내가 검사한 칼럼들
    for(int i=0; i<p.size();i++){ //p는 후보키들의 집합.
        int cnt=0;
        for(int j=0; j<p[i].size();j++){
            for(int k=0; k<r.size();k++){
                if(p[i][j]==r[k]) //하나하나 비교해서
                    cnt++;
            }
        }
        if(cnt==p[i].size()) //만약 이미 있는 칼럼이라면 최소성을 만족하지 못함.
           return 0;
    }      
    p.push_back(r); //후보키를 넣어줌.
    return 1;
}
int solution(vector<vector<string>> relation) {
    int answer = 0;
    row=relation.size(),col=relation[0].size();//relation 테이블에 행과 열의 크기를 기록
    vector<int>v;
    vector<int>visit;
    for(int i=0; i<col;i++)
        v.push_back(i);
    visit.assign(col,0);
    vector<int>num; //num은 칼럼들의 조합을 기록할 vector
    for(int i=1; i<=col;i++){
        visit[visit.size()-i]=1;
        do{ 
            for(int i=0; i<v.size();i++){
                if(visit[i]!=0)
                    num.push_back(v[i]);
            }
            answer+=funct(relation,num);
            num.clear(); //배열을 초기화해서 다시 조합을 넣어줍니다.
        }while(next_permutation(visit.begin(),visit.end()));
    }
    return answer;
}

 

💡혹시 제가 잘못 판단했거나, 지적사항이 있으면 댓글 달아주세요!