[ 프로그래머스 / 문자열 ] 후보키 (KaKao)

1. 문제

---

 

코딩테스트 연습 - 후보키

 

 

2. 소스코드

---

- 굉~장히 직관적으로 짰다. 대충 효율성이 좋지 않다라는 뜻.

- 문제의 크기가 매우 작아서, 가지치기를 하지않고 다 구한 뒤에 후보키를 추렸다.

 

- 1) 경우의 수를 dfs를 이용, 구한다.

- 2) map을 이용해서, 해당 경우의 수가 후보키가 될 수 있는지 판단. 후보키라면 저장.

- 3) 후보키들끼리 포함관계를 따져서, 최소성을 보장하는 후보키만 남긴다.

 

 

소스코드

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

vector<vector<string>> copy_rel;
vector<string> candi_keys;

bool compare(string& a, string& b) {
    if (a.length() != b.length())
        return a.length() < b.length();
    return a > b;
}

bool isIn(string find, string base) {
    for (int i = 0; i < find.size(); ++i)
        if (base.find(find[i]) == string::npos) 
            return false;
    return true;
}

bool isKey(string str_key) {
    if (str_key == "") return false;
    vector<int> key;
    for (char ch : str_key)
        key.push_back(ch - '0');

    unordered_map <string, int> map;

    for (int i = 0; i < copy_rel.size(); ++i) {
        string temp = "";
        for (int j = 0; j < key.size(); ++j) {
            temp += '_' + copy_rel[i][key[j]];
        }
        map[temp]++;
    }
    if (map.size() == copy_rel.size()) return true;
    else return false;
}

void dfs(string key, int prev, int depth) {
    if (depth >= copy_rel[0].size()) {
        if (isKey(key)) candi_keys.push_back(key);
        return;
    }
    dfs(key, prev + 1, depth + 1);
    dfs(key + to_string(prev), prev + 1, depth + 1);
}

int solution(vector<vector<string>> relation) {

    copy_rel = relation;
    // 1) 경우의 수를 구하고, 예비 후보키들을 선정한다.
    dfs("", 0, 0);

    // 2) 예비 후보키들을 길이, 순서에 따라 정렬한다.
    sort(candi_keys.begin(), candi_keys.end(), compare);
    int size = candi_keys.size();
    int answer = size;

    // 3) 예비 후보키들에 대한, 최소성을 검사한다.
    for (int i = 0; i < size; ++i) {
        if (candi_keys[i] == "-1") continue;
        for (int j = 0; j < size; ++j) {
            if (i == j or candi_keys[j] == "-1") continue;
            if (isIn(candi_keys[i], candi_keys[j])) {
                candi_keys[j] = "-1";
                answer--;
            }
        }
    }

    return answer;
}