프로그래머스 - 후보키

문제 링크입니다 : programmers.co.kr/learn/courses/30/lessons/42890

코딩테스트 연습 - 후보키

 

set + 구현 문제였다.

 

 

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

using namespace std;

vector<pair<vector<bool>, int>> candKey;

vector<vector<bool>> minimal;

vector<bool> choosed;
int n;
int m;

bool compare(pair<vector<bool>, int>& a, pair<vector<bool>, int>& b) {
    if(a.second == b.second) {
        return a.first < b.first;
    }
    return a.second < b.second;
}

bool isMinimal(const vector<bool>& temp) {
    for(int i = 0; i < minimal.size(); i++) {
        
        bool hasRelation = true;
        for(int j = 0; j < minimal[i].size(); j++) {
            if(minimal[i][j] && !temp[j]) {
                hasRelation = false;
                break;
            }
        }
        
        if(hasRelation) {
            return false;
        }
    }
    
    return true;
}

bool isUnique(const vector<vector<string>>& relation, vector<bool>& temp) {
    set<string> s;
    for(int i = 0; i < n; i++) {
        string str = "";
        for(int j = 0; j < temp.size(); j++) {
            if(temp[j]) {
                str += relation[i][j];
            }
        }
        if(s.find(str) != s.end()) return false;
        s.insert(str);
    }
    return true;
}

void getAllCandKey(const vector<vector<string>>& relation, int index) {
    if(index == m) {
        vector<int> tempIndex;
        int cnt = 0;
        for(int i = 0; i < m; i++) {
            if(choosed[i]) cnt++;
        }
        if(cnt != 0) {
            if(isUnique(relation, choosed)) {
                candKey.push_back({choosed, cnt});
            }
        }
        return;
    }
    
    choosed[index] = true;
    getAllCandKey(relation, index + 1);
    choosed[index] = false;
    getAllCandKey(relation, index + 1);
    
}


int solution(vector<vector<string>> relation) {
    int answer = 0;
    n = relation.size();
    m = relation[0].size();
    
    choosed.assign(m, false);
    
    getAllCandKey(relation, 0);
    
    
    sort(candKey.begin(), candKey.end(), compare);    
    
    for(int i = 0; i < candKey.size(); i++) {
        const vector<bool>& temp = candKey[i].first;
        if(isMinimal(temp)) {
            minimal.push_back(temp);
        }
    }
    
    answer = minimal.size();
    
    return answer;
}

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~