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

문제설명

제한사항

• relation은 2차원 문자열 배열이다.
• relation의 컬럼(column)의 길이는 1 이상 8 이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.
• relation의 로우(row)의 길이는 1 이상 20 이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.
• relation의 모든 문자열의 길이는 1 이상 8 이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.
• relation의 모든 튜플은 유일하게 식별 가능하다.(즉, 중복되는 튜플은 없다.)

입출력 예

relationresult

[["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]]

2

입출력 예 설명

입출력 예 #1
문제에 주어진 릴레이션과 같으며, 후보 키는 2개이다.

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

using namespace std;

bool check(vector<int> vec, int now)
{
    for(int i=0; i<vec.size(); i++)
    {
        if((vec[i] & now) ==vec[i])
        {
            return false;
        }
    }
    return true;
}

int solution(vector<vector<string>> relation) {
    int answer = 0;
    
    int rowSize = (int)relation.size();
    int colSize = (int)relation[0].size();
    vector<int> ans;
    
    for(int i=1; i< (1<<colSize); i++)
    {
        set<string> s;
            
            for(int j=0; j<rowSize; j++)
            {
                string now="";
                
                for(int k=0;k<colSize;k++)
                {
                    if(i & (1<<k))
                    {
                        now += relation[j][k];
                    }
                }
                s.insert(now);
            }
    
    if(s.size() == rowSize && check(ans, i))
        ans.push_back(i);
    }
    return (int)ans.size();
}