[프로그래머스][C++] 후보키

 

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

코딩테스트 연습 - 후보키

 

 

글쓴이의 답

개인적인 풀이 임으로

이것보다 더 좋은 알고리즘은 많음...

이렇게도 풀이하는구나.. 공유하기 위해 올림...

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

using namespace std;


int dfs(vector<bool> &check, int &columnCount, int location, vector<vector<int>> &caseNum, vector<int> save){
    caseNum.push_back(save);
    
    for(int i=location; i < columnCount; i++){
        if(true == check[i]){
            continue;
        }
        check[i] = true;
        save.push_back(i+1);
        dfs(check, columnCount, i, caseNum, save);        
        save.pop_back();
        check[i] = false;
    }
    
    
    return 0;
}

int solution(vector<vector<string>> relation) {
    int answer = 0;
    
    int columnCount = (int)relation[0].size();
    int dataCount = (int)relation.size();
    
    vector<vector<int>> caseNum;
    vector<bool> check(columnCount, false);
    
    vector<int> save;
    
    for(int i=0; i < columnCount; i++){        
        check[i] = true;
        save.push_back(i+1);
        dfs(check, columnCount, i, caseNum, save);
        save.pop_back();
        check[i] = false;
    }       
    
    
    
    while(0 != caseNum.size()){
        int minSize = 9999;  
        for(vector<int> getSize : caseNum){
            if(getSize.size() < minSize){
                minSize = getSize.size();
            }
        }
        vector<int> numData;
        int i=0;
        for(i=0; i< caseNum.size(); i++){
            if(caseNum[i].size() == minSize){
                numData = caseNum[i];
                break;
            }
        }
        
        caseNum.erase(caseNum.begin()+i);
        set<string> resultString;
        
        for(vector<string> data : relation){
            string temp = "";
            for(int num : numData){
                temp+=data[num-1];
            }
            resultString.insert(temp);
        }
        
        if(dataCount == resultString.size()){
            answer++;
            
            
            
            bool findCheck = false;
            while(true != findCheck){
                findCheck = true;
                
                for(int i=0; i < caseNum.size(); i++ ){
                    vector<int> del = caseNum[i];
                   
                    bool resultX = false;
                    for(int f : numData){
                        resultX = false;
                        for(int n : del){
                            if(n == f){
                                resultX = true;
                            }
                        }
                        if(false == resultX){
                            break;
                        }
                    }
                    if(true == resultX){
                        findCheck = false;
                        caseNum.erase(caseNum.begin() + i);
                        break;
                    }
                }
            }
        }
        
    }
    
    return answer;
}

꾸준히 하다보면 실력이 늘겠지..