2019 KAKAO BLIND RECRUITMENT 후보키

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

코딩테스트 연습 - 후보키

 

map 중복 체크 스트링으로 묶어서 하는 아이디어 !

 

#include <string>
#include <vector>
#include<iostream>
#include<string.h>
#include<map>
using namespace std;
int N, M;
vector<int> res;
vector<int> che;
vector<vector<string> > vec;
bool flag_1,flag_2;
int answer = 0;

void check(int idx, int cur)
{
    if(!flag_2)
    {
        return;
    }
    
    if(cur < res.size())
    {
        bool flag = true;
        map<string,bool> m;
        for(int i = 0; i < N; i++)
        {
            string str = "";
            for(int j = 0; j < che.size(); j++)
            {
                str += vec[i][che[j]] + " ";
             }
            if(m[str])
            {
                flag = false;
                break;
            }
            m[str] = true;
         }
        if(flag)
        {
            flag_2 = false;
            return;
        }
    }
    
    for(int i = idx + 1; i < res.size(); i++)
    {
        che.push_back(res[i]);
        check(i,cur + 1);
        che.pop_back();
    }
}

void DFS(int idx , int cur)
{
   // 유일성 만족 
 
    
    flag_1 = true;
    map<string,bool> m;
    for(int i = 0; i < N; i++)
    {
        string str = "";
        for(int j = 0; j < res.size(); j++)
        {
            str += vec[i][res[j]] + " ";
        }
        if(m[str])
        {
            flag_1 = false;
            break;
        }
        m[str] = true;
    }
   
    //최소성 만족
    
    flag_2 = true;
    for(int i = 0; i < res.size(); i++)
    {
        che.push_back(res[i]);
        check(i,1);
        che.pop_back();
    }
    
    
    if(flag_1 && flag_2)
    {
        answer++;
    }
  
    
    for(int i = idx + 1; i < M; i++)
    {
        res.push_back(i);
        DFS(i,cur + 1);
        res.pop_back();
    }
}

int solution(vector<vector<string>> relation) {
    
    N = relation.size();
    M = relation[0].size();
    vec = relation;
    
    for(int i = 0; i < M; i++)
    {
        res.push_back(i);
        DFS(i,1);
        res.pop_back();
    }
    
    return answer;
}