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

문제 설명

• 관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.
  • 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
  • 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

아래와 같은 데이터가 주어졌을 때, 후보 키의 최대 개수를 구하라.

위의 예를 설명하면, 학생의 인적사항 릴레이션에서 모든 학생은 각자 유일한 학번을 가지고 있다. 따라서 학번은 릴레이션의 후보 키가 될 수 있다.
이름에 대해서는 같은 이름(apeach)을 사용하는 학생이 있기 때문에,이름은 후보 키가 될 수 없다.

그러나, 만약 [이름,전공]을 함께 사용한다면 모든 튜플을 유일하게 식별 가능하므로 후보 키가 될 수 있게 된다.
물론 [이름,전공,학년]을 함께 사용해도 릴레이션의 모든 튜플을 유일하게 식별할 수 있지만, 최소성을 만족하지 못하기 때문에 후보 키가 될 수 없다.
따라서, 위의 학생 인적사항의 후보키는 학번, [이름,전공] 두 개가 된다.

릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하라.

제한사항

• relation은 2차원 문자열 배열이다.
• relation의 컬럼(column)의 길이는1이상8이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.
• relation의 로우(row)의 길이는1이상20이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.
• relation의 모든 문자열의 길이는1이상8이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.
• relation의 모든 튜플은 유일하게 식별 가능하다.(즉, 중복되는 튜플은 없다.)

입출력 예

relation	result
[["100","ryan","music","2"], ["200","apeach","math","2"], ["300","tube","computer","3"], ["400","con","computer","4"], ["500","muzi","music","3"], ["600","apeach","music","2"]]	2

입출력 예 설명

문제에 주어진 예시와 같다.

풀이

처음엔 '설마 완전탐색 이겠어?'라고 생각했다. 그래서 다른 알고리즘을 생각해보려고 애를 썼다. 하지만 더 나은 방법이 생각나지 않았고, 시간 복잡도를 대강 계산해봤을 때, 입력 크기가 작기 때문에 완전탐색으로 가능한 시간 복잡도가 나와서 완전 탐색으로 풀었다.

* 실전이라고 생각하면, 굉장한 시간낭비를 한 셈이다. 먼저 시간 복잡도를 계산해서 완전탐색이 가능한지 판단하자

알고리즘

1. 가능한 모든 경우의 수 생성 , 정렬

2. 한 가지 경우의 수에 대해해당 경우의 수가 후보키가 되는지 판별, 

    후보키 O -> 해당 경우의 수가 포함되는 모든 경우의 수 제거, answer++

    후보키 X -> 해당 경우의 수 제거 (이유 : 아래 del_cases() 설명 참조) 

이렇게 써놓고 보니 간단한 것 같기도.. 머리가 아팠는데..

함수

• combination()
  • 모든 경우의 수 생성을 위한 함수
• cmp()
  • 모든 경우의 수를 sort할 때 기준이 되는 함수
• is_candidate()
  • 해당 경우의 수가 후보키인지를 판단하는 함수
  • 주어진 relation에서 해당 column들만 모아 각 row별로 하나의 string을 만들어 vector에 담고, 해당 vector에서 중복된 값을 제거한 후의 길이가 원래 row의 개수와 같으면 후보키인 것으로 판별 (중복된 값이 없다는 뜻)
• del_cases()
  • 해당 후보키가 포함되는 모든 경우의 수를 제거하는 함수
  • 여기에서 all_cases를 맨 앞부터 검사하기 때문에, 불필요한 연산을 피하기 위해 후보키가 아닌 경우의 수를 all_cases에서 바로바로 삭제해줌

코드

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

int row_n;
int cal_n;
vector<vector<int>> all_cases;

//가능한 모든 조합 생성
void combination(int n = 0, vector<int> temp = {}) {
    for (int i = n;i < cal_n;i++) {
        temp.push_back(i);
        all_cases.push_back(temp);
        combination(i+1,temp);
        temp.pop_back();
    }
}
// all_cases 정렬을 위한 함수
bool cmp(vector<int> first, vector<int> second) {
    if (first.size() == second.size()) {
        for (int i = 0;i < first.size();i++) {
            if (first[i] == second[i])
                continue;
            else if (first[i] > second[i])
                return false; //second가 먼저 
            else
                return true; //first가 먼저
        }
    }
    else if (first.size() > second.size())
        return false; //second가 먼저 
    else
        return true; //first가 먼저

}

//해당 column의 조합이 후보키가 될 수 있는지 판단 
bool is_candidate(vector<int> columns, vector<vector<string>> relation) {
    vector<string> sets;
    for (int i = 0;i < row_n;i++) {
        string temp;
        for (int j = 0;j < columns.size();j++) {
            temp += relation[i][columns[j]] + " ";
        }
        sets.push_back(temp);
    }
    sort(sets.begin(), sets.end());
    sets.erase(unique(sets.begin(), sets.end()), sets.end());
    if (sets.size() == row_n)
        return true;
    return false;
}
//해당 후보키가 들어있는 모든 경우의 수 삭제 
void del_cases(vector<int> candidate_key) {
    vector<int> erase_index;
    int count = 0;
    for (int i = 0;i < all_cases.size();i++) {
        bool flag = true;
        for (int j = 0;j < candidate_key.size();j++) {
            vector<int>::iterator iter;
            iter = find(all_cases[i].begin(), all_cases[i].end(), candidate_key[j]);
            if (iter == all_cases[i].end())
                flag = false;
        }
        if (flag)
            erase_index.push_back(i);
    }
    for (int i = 0;i < erase_index.size();i++) {
        int e = erase_index[i] - count;
        all_cases.erase(all_cases.begin() + e);
        count++;
    }
}
int solution(vector<vector<string>> relation) {
    int answer = 0;
    cal_n = relation[0].size();
    row_n = relation.size();
    combination(); // 모든 경우의수 생성
    sort(all_cases.begin(), all_cases.end(), cmp);

    for (int i = 0;i < all_cases.size();i++) {
        if (is_candidate(all_cases[i], relation)) {
            del_cases(all_cases[i]);
            i--;
            answer++;
        }
        else {
            all_cases.erase(all_cases.begin() + i);
            i--;
        }
    }
    return answer;
}

결과