[2019 카카오 블라인드 채용 코딩테스트] 후보키 C++ 풀이 및 정답 코드

문제 링크

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

프로그래머스

 

 

 

문제 설명

16.09%의 정답률을 가졌다.
세번 째 문제던데 보통 여기서 무너졌을 듯 (아마 나도)

데이터베이스 수업을 들었다면 이해가 좀 빠를 것 같은데, 청년 치매를 앓고있는 나에겐 너무나 새로웠다...

후보키를 캐주얼하게 설명하면 속성 차집합 중 튜플들을 유일하게 식별할 수 있으면서 필요없는 속성은 들어가있지 않은 것을 의미한다.

처음 접하는 사람이라면 유일성은 이해가 쉽지만 최소성이 이해하기 까다로운데, 최소성은 예를 들어 속성 {a, b, c, d, e} 중 {b, d}가 후보키라면 {a, b, d}는 최소성에 위반해 후보키가 될 수 없는 것을 의미한다. 마찬가지로 {b, c, d} 나 {a, b, c, d} 도 후보키가 될 수 없다.

 

 

 

문제 풀이

문제 해결은 총 네 가지의 줄기가 있다.

1. 모든 차집합 검사
후보키는 속성 집합의 차집합이므로 일단 모든 차집합 조합을 검사하는 것으로 시작해야한다.
문제의 제한 사항을 보면 시간 복잡도가 어떻게 나와야하는지 파악이 가능한데, 속성의 갯수는 최대 8개이므로 공집합을 제외한 차집합의 갯수는 255개이다. 튜플의 갯수가 최대 20개 이므로, 모든 차집합 조합을 검사해도 문제는 없을 것임을 알 수 있다.
나는 "모든 조합을 검사한다"라는 키워드가 들어가면 무조건 재귀를 쓰는 편이다.
따라서 재귀를 이용한 dfs를 사용, 브루트포스로 구현해도 문제 없을 듯한 제한사항이므로 메모이제이션은 고려하지 않는다.

2. 유일성 검사
튜플의 유일성은 어떻게 검증할 수 있을까?
중복이 불가능한 요소들을 검증해야하므로 unordered_set을 사용하면 쉬울 것이다.
각 튜플에서 해당하는 속성을 뽑아 string으로 붙여 만들고 set에 넣어 중복성 검사를 하면 될 것이다.

3. 최소성 검사
까다롭다. 
나는 연산을 줄이기위해 재귀에서 한번 걸러주고, 재귀가 끝난 후 부분집합 검사를 통해 최소성 검사를 했다.

3-1. 재귀에서 걸러주기
재귀로 모든 차집합을 검사할 때, 작은 차집합부터 큰 차집합으로 검사하게되어있다.
예를 들어 속성 {a, b, c, d, e}의 차집합을 재귀로 순환한다고 생각할 때, 차집합 {b, d}는 차집합 {b, d, e} 순환 전에 오게 되어있다.
그러면 차집합 {b, d}가 후보키에 해당될 때 {b, d, e}는 유일성은 충족하지만 최소성에 위반되어 후보키가 될 수 없으므로 {b, d} 검사에서 순환을 멈춰야한다.
따라서 현재 차집합이 유일성을 충족하면, 해당 차집합을 포함하는 차집합은 검사하지 않는다.
즉, 유일성 검사를 불통했을 때만 다음 인덱스를 포함시켜 재귀를 시켜주면 된다.
하지만 이 방법은 한가지 문제가 있는데, 한 방향으로 검사하므로 {b, c}가 후보키일 때 {a, b, c}도 후보키에 포함시키는 것을 막을 방법이 없다. 

3-2. 최소성 검사
따라서 재귀가 끝난 후 부분집합 검사를 해서 더 큰 집합을 제거해야한다.
그러기 위해선 원소 갯수로 차집합들을 정렬하고 집합[i]에 대해서 집합[j] (j > i)가 집합[i]를 포함하면 집합[j]를 제거하면 될 것이다.
집합을 원소 갯수 오름차순으로 정렬하기 위해서 compareVectorSize 함수를 정의하고 sort 메소드의 마지막 인자로 주었다.

자세한 사항은 코드 주석을 확인하세요.

 

 

 

코드

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

using namespace std;

// 속성의 차집합, 후보키들
vector<vector<int>> answers;

// 1. 재귀로 최대 8개 속성의 모든 차집합 검사
void dfs(vector<vector<string>> &relation, vector<int> indexes, int index)  {
    // 속성의 인덱스
    if (index > relation[0].size())
        return;
    unordered_set<string> set;
    for (auto r : relation) {
        string str;
        // 2. 유일성 검사: 각 학생의 속성 조합해서 string 생성. 같으면 set에서 걸러질 것임
        for (auto i : indexes) {
            str += r[i];
        }
        
        if (set.count(str) == 0) {
            set.insert(str);
        } else {
            // 3-1. 최소성 충족: 중복 있을 때만 다음으로 가게 함
            dfs(relation, indexes, index+1);
            indexes.push_back(index);
            dfs(relation, indexes, index+1);
            return;
        }
    }
    
    answers.push_back(indexes);
    return;
}

bool compareVectorSize (vector<int> &v1, vector<int> &v2) {
    return v1.size() < v2.size();
}

int solution(vector<vector<string>> relation) {
    dfs(relation, {}, 0);
    // 원소 갯수로 오름차순 정렬
    sort(answers.begin(), answers.end(), compareVectorSize);
    
    // 3-2. 최소성 충족: 중복 검사
    for (int i=0; i<answers.size()-1; i++) {
        for (int j=i+1; j<answers.size(); j) {
            // 부분집합 검사
            if (includes(answers[j].begin(), answers[j].end(), answers[i].begin(), answers[i].end())) {
                answers.erase(answers.begin() + j);
            } else {
                j++;
            }
        }
    }
    
    return answers.size();
}

 

 

 

시공간 복잡도

*속성의 갯수를 n, 튜플의 갯수를 m이라고 할 때

시간 복잡도: O(2^n * 2^n * 2^n) 
최소성 검사에서 O(N*N*N)인데 answers의 갯수인 N의 최대가 2^n이므로

공간 복잡도: O(n * 2^n)

이것만 보면 끔찍한 알고리즘으로 보이지만 n<=8, m<=20 이므로 문제없다... (있나요?)

 

 

 

결과

 

 

 

다른 사람의 코드

 

 

 

리뷰

한시간 반 정도 걸린 것 같다. 어려웠다.

총 세시간 동안 스터디에서 카카오 코테를 풀었고 후보키까지 딱 세문제를 풀었다.

커트라인이 궁금하다.