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

😎 문제 설명

😀 풀이 과정

후보키를 고르는 모든 조합을 비트마스크 집합을 이용하여 표현하였다.

아무것도 고르지 않는 i = 0를 제외한 모든 조합을 for문을 이용해 순회하며, 유일성과 최소성을 검사하여 사용이 가능한 후보키라면 답에 추가해주었다.
비트마스크의 원소 하나하나는 최대 8개의 Attribute의 집합을 표현하고 있고, 원소가 1이면 후보키, 0이면 후보키가 아닌 것으로 가정하였다.

• 어떻게 유일성을 검사하나요 ?
  • i번, j번 Attribute가 후보키라고 가정하자. 모든 튜플의 i번, j번 속성에 해당하는 문자열을 이어붙인다. 그 결괏값 중에 중복되는 문자열이 하나라도 있으면 (i, j)는 후보키가 될 수 없다.
  • 예를 들어서, ["이름", "전공"]을 후보키로 한 경우에 예제 입력에 주어진 테이블의 후보키의 속성에 해당하는 문자열을 이어붙이면 아래와 같다.

["100","ryan","music","2"] => "ryanmusic"
["200","apeach","math","2"] => "apeachmath"
["300","tube","computer","3"] => "tubecomputer"
["400","con","computer","4"] => "concomputer"
["500","muzi","music","3"] => "muzimusic"
["600","apeach","music","2"] => "apeachmusic"

위 예제에서 apeach라는 이름이 중복됨에도 불구하고, 전공이 "math"와 "music"으로 갈리기 때문에 문자열을 합치면 서로 다른 문자열을 가지게 됨을 알 수 있다. 이 아이디어를 이용해 문자열의 일치 여부로 유일성을 체크 할 수 있었다.

 

• 어떻게 최소성을 검사하나요 ?
  • 이전에 검사했던 조합 중에서, 지금 선택한 조합의 일부분을 사용해 이미 조건을 만족한 후보키가 있다면 지금 조합은 선택하지 않는다.
  • 내 풀이의 경우, answer++가 아닌 candidates에 후보키 집합을 비트마스크로 표현하여 정수 형태로 저장해주었다. 모든 집합을 순회하는 for문은 집합이 적은 것에서 큰 것으로 올라가고 있기 때문에, 최소성을 위반할 가능성이 높은 집합은 무조건 후순위에 발견된다.
  • 이를 이용해서, isSubset 함수를 만들어 두 집합을 비교하여 target이 previous의 원소를 포함하는지 체크하였다.
  • check_minimality함수에서는 현재 후보키 집합을 이전에 저장한 후보키들과 비교하여 최소성을 만족하는 지 검사하였다.

😆 해결 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

vector<int> candidates; // 이미 검사한 후보키를 등록한다.

bool isSubset(int target, int previous) {
    return ((target & previous) == previous);
}

bool check_minimality(int target) { // 이전에 등록한 후보키와 겹치면 false
    for (int previous : candidates) {
        if (isSubset(target, previous))
            return false;
    }
    return true;
}

bool check_uniqueness(int i, vector<vector<string>> relation) {
    int k = relation[0].size();
    vector<string> combined;

    for (auto v : relation) {
        string temp = "";
        for (int j = 0; j < k; j++)
            if ((i & (1 << j)) != 0) 
                temp += v[j];
        if (find(combined.begin(), combined.end(), temp) != combined.end())
            return false; 
        else
            combined.push_back(temp);
    }
    return true; 
}

int solution(vector<vector<string>> relation) {
    int k = relation[0].size(); // Attribute의 개수
    for (int i = 1; i < (1 << k); i++) {
        if (check_uniqueness(i, relation) && check_minimality(i)) 
            candidates.push_back(i);
    }
    int answer = candidates.size();
    return answer;
}