[프로그래머스] 후보키

난이도: Level 2

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42890

코딩테스트 연습 - 후보키

 

RDB의 이론 기본 지식을 알고 있으면 문제를 조금 더 빨리 이해할 수 있습니다.

 

RDB에서, 후보 키 개념을 간단하게 설명해 보겠습니다.

각 칼럼 (DB에서는 attribute; 속성이라고 합니다)은 특정 튜플 (tuple)에 대한 정보를 포함합니다.

예를 들어서 아래와 같은 표가 있다면,

 

학번	이름	학과	학년
2014123456	김화석	컴퓨터공학과	4
2015167848	복학생	통계학과	3
2022020321	복학생	전기전자공학부	1
2022042125	새내기	컴퓨터공학과	1

총 4명의 사람이 존재하고, 각 사람은 이름/학과/학년 이라는 값을 가집니다.

이 중 특정 사람을 다른 사람들로부터 분명히 식별할 수 있는 칼럼이 있다면, 해당 칼럼을 후보 키라고 합니다.

즉 primary key; 기본 키가 될 수 있는 후보라는 의미입니다.

이 후보 키는 단 하나의 칼럼일 수도 있지만, 두개 이상의 칼럼의 집합일 수도 있습니다.

 

후보 키는 다음 두 사항을 만족해야 합니다.

• 유일성: 특정 사람을 다른 사람들로부터 분명히 식별할 수 있는 칼럼
• 최소성: 현재 키를 부분집합으로 쪼갰을 때, 쪼개진 부분집합이 유일성을 가지지 않는 경우

주어진 문제의 조건을 보면, 칼럼은 최대 8개가 존재합니다.

즉, 원소가 8개인 집합의 부분집합의 개수를 계산해 보면, 공집합을 제외하고 2^8 - 1 = 255개의 경우의 수가 나옵니다.

각 경우의 수에 대해, 부분집합을 완성한 후, 유일성과 최소성을 만족하면 정답 값을 하나 증가시키는 식으로 작성하였습니다.

 

dfs를 통해 부분집합을 구성하였는데, 부분집합의 원소의 수는 for문을 이용하여 1부터 column의 수까지 반복하도록 하였습니다. 이 때, 중복되는 원소를 추가하지 않도록 bool 형의 is_selected 배열을 사용하였습니다.

정해진 원소의 수를 만족하면, 유일성과 최소성을 만족하는지 각각 확인하는 함수를 통해 확인을 하였고, 둘을 만족하는 경우 candidates 배열에 주어진 columnCombination을 넣고 answer 값을 하나 증가시킵니다.

 

유일성은 아래와 같이 작성하였습니다.

임시 unorder_set<string> temp을 선언하고, relation만큼 루프를 돕니다.

루프를 돌며, columnCombination의 실제 column 값을 꺼내어 result에 담고, 이 result 값이 temp에 이미 존재한다면, 루프를 종료시키고 false를 리턴합니다.

위 루프를 모두 통과한다면 유일한 것으로 인정하고, true를 반환합니다.

 

최소성은 아래와 같이 작성하였습니다.

우선 원소가 1개만 존재한다면, 해당 조합은 더 작게 나누어질 수 없으므로 true를 리턴합니다.

candidates는 지금까지 이미 최소성&유일성을 통과한 조합을 담고 있는 배열인데, 배열의 각 원소를 확인하며 만약 candidates의 원소가 columnCombination 내에 없다면, candidates의 원소를 확인하는 루프를 탈출합니다.

위 루프를 모두 통과한다면 유일한 것으로 인정하고, true를 반환합니다.

 

코드 링크: GitHub

GitHub - kchung1995/code_test_personal: 혼자 코딩 테스트 공부를 하며 사용하는 저장소

// 문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42890
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_set>

using namespace std;

vector<vector<string>> relation;
unordered_set<int> columnCombination;
vector<unordered_set<int> > candidates;
vector<bool> is_selected;
int columns = -1;
int answer = 0;

bool isUnique(vector<vector<string> > &relation) {
    unordered_set<string> temp;
    for (int i = 0; i < relation.size(); i++) {
        string result = "";
        for (auto &next : columnCombination) {
            result += relation[i][next];
        }

        if (temp.find(result) != temp.end()) return false;
        else temp.insert(result);
    }

    return true;
}

bool isMinimal() {
    // 1개의 column으로 이루어져 있다면 무조건 최소성을 만족
    if (columnCombination.size() == 1) return true;
    
    for (int i = 0; i < candidates.size(); i++) {
        bool minimal = false;
        for (auto &key : candidates[i]) {
            if (columnCombination.find(key) == columnCombination.end()) {
                minimal = true;
                break;
            }
        }
        if (!minimal) return false;
    }
    return true;
}

// start: 시작 위치, count: 현재까지 누적 컬럼 개수, totalCount: 목표 개수
void dfs(int start, int count, int totalCount, vector<vector<string> > &relation) {
    // 조합이 만들어졌을 때,
    if (count == totalCount) {
        // 만들어진 조합이 유일성과 최소성을 만족하면 센다
        if (isUnique(relation) && isMinimal()) {
            candidates.push_back(columnCombination);
            answer++;
        }
        return;
    }
    
    // 조합에 칼럼을 하나씩 더 추가한다
    for (int i = start; i < columns; i++) {
        if (is_selected[i] == true) continue;
        is_selected[i] = true;
        columnCombination.insert(i);
        dfs(i, count+1, totalCount, relation);
        is_selected[i] = false;
        columnCombination.erase(i);
    }
}

int solution(vector<vector<string>> relation) {
    
    // db에 주어진 relation의 수
    columns = relation[0].size();
    // 선택 여부를 기록하는 bool형 배열
    is_selected.resize(columns, false);

    
    // dfs를 이용하여 가능한 조합의 경우의 수를 구한다. 
    for (int i = 1; i <= columns; i++) {
        dfs(0, 0, i, relation);
    }
    
    return answer;
}

 

유일성과 최소성을 어떻게 확인할까 고민도 많이 하고... 어려웠던 문제입니다.

중복 확인은 역시 unordered set이 최고네요. 상수 시간 내에 간편하게 확인할 수 있어서 좋은 것 같아요 ㅎㅎ

 

 

참고한 글:

• https://yabmoons.tistory.com/688