[Programmers] 후보키

김민석·2022년 1월 2일
0

프로그래머스

목록 보기
30/30

데이터베이스에서 활용할 후보키의 개수를 구하는 문제이다.

문제풀이 전략

후보키의 조건은 다음과 같다.

  1. 유일성 - 유일하게 식별 가능
  2. 최소성 - 속성 중 하나라도 제거하면 유일성이 깨짐
  3. 유일성과 최소성을 모두 만족하는 속성 또는 속성의 집합

위의 세가지 조건을 만족하는 후보키의 개수를 찾으면 된다.

후보키 가능 경우 선택 하기

후보키가 될 수 있는 경우를 택하기 위해 우선 permutation을 사용하였다.

속성의 갯수가 n개 라고 했을 때 후보키로 사용할 수 있는 속성의 갯수는
1,2,3 ... n 개 까지 가능하다.

그리고 각 경우마다 어떤것을 택할 지 골라야 한다.

예를들어 현재 확인하고자 하는 개수가 3개라고 할 때 0,1,2 로 뽑을지 1,2,3으로 뽑을지 4,8,10으로 뽑을지 골라야 한다.

이 과정을 permutation을 사용하였다.

최소성 만족 시키기

그리고 나서 현재 선택한 속성들이 최소성을 만족시키는지 판단해 준다.

만약 이미 후보키로 판명된 것들이 현재 확인하고자 하는 속성들에 모두 포함되어 있을 경우 확인하는 속성들은 후보키가 될 수 없다.

유일성 만족 시키기

위의 두 과정을 모두 마친 속성들을 전체 데이터에 적용하여 유일하게 식별이 가능한지 판단한다.

이 과정은 단순 반복문을 통해 가능하다.

회고

permutaion을 사용하여 조합을 사용하기 위해 1과 0으로 구성된 벡터를 활용하였는데, 이 때 중복이 많이 발생한다.

이것을 해결해 주기 위해 set 자료구조를 사용하였다.

그리고 최소성을 만족시키기 위해 현재까지 후보키로 등록된 값들을 저장하는데도 set 자료구조를 활용하였다.

마지막으로 유일성을 만족시키는지 판단하기 위한 자료구조 역시 set을 사용하였다.

set이 세번이나 사용되었고, 네이밍 역시 너무 대충 해놔서 헷갈리는 경우가 많았다. 좀 더 깔끔하게 코드를 짤 수 있도록 노력해야겠다.

코드

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

using namespace std;

int solution(vector<vector<string>> relation) {
    int answer = 0;
    
    int n = relation[0].size();
    set<string> ss;
    set<string> sss;
    for(int i=0;i<n;i++){
        vector<int> v;
        for(int j=0;j<n;j++){
            if(j <= i)
                v.push_back(1);
            else
                v.push_back(0);
        }
        
        do{
            string st = "";
            for(int j=0;j<v.size();j++){
                if(v[j] == 1)
                    st += j + '0';
            }
            
            if(ss.find(st) != ss.end())
                continue;
            ss.insert(st);
            
            int fl = 0;
            for(auto iter = sss.begin();iter != sss.end();iter++){
                int siz = 0;
                for(int x=0;x<(*iter).size();x++){
                    if(st.find((*iter)[x]) == string::npos)
                        continue;
                    siz++;
                }
                if(siz == (*iter).size())
                    fl = 1;
            }
            if(fl == 1)
                continue;
            
            set <string> s;
            int flag = 0;
            for(int j=0;j<relation.size();j++){
                string str = "";
                for(int k=0;k<st.size();k++){
                    str += relation[j][st[k]-'0'];
                }
                if(s.find(str) == s.end()){
                    s.insert(str);
                }else{
                    flag = 1;
                    break;
                }
            }
            if(flag == 0){
                sss.insert(st);
                answer++;
            }
        }while(prev_permutation(v.begin(), v.end()));
    }
    return answer;
}

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

profile
김민석의 학습 정리 블로그

0개의 댓글