[프로그래머스 2레벨] 후보키 (C++)

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

using namespace std;

int solution(vector<vector<string>> relation) {
    int answer = 0;
    
    int row = relation.size(); //튜플
    int col = relation[0].size(); //속성
    vector<int>v;
    
    for(int i=1; i<(1<<col); i++) //속성 조합
    {
        set<string>s;
        
        for(int j=0; j<row; j++)
        {
            string key = "";
            for(int k=0; k<col; k++)
            {
                if(i & (1<<k)) key += relation[j][k]; //현재 튜플에 대한 속성값 저장
            }
            s.insert(key);
        }
        
        if(s.size()!= row) continue; //유일성 체크
        bool isM = 1;
        for(int prev : v)
        {
            if((i&prev) == prev) //최소성 체크
            {
                isM = 0;
                break;
            }
        }
        
        if(isM) v.push_back(i);
        
    }
    answer = v.size();
    return answer;
}

 

비트마스킹을 또한 조합 생성으로 풀 수 있는 문제이다.

먼저 속성의 조합 경우의 수를 따져야한다.

예제의 케이스를 보면 학번, 이름, 전공, 학년 4가지에 대해서의 조합이므로 2^4로 총 16가지이다.

이를 비트마스킹으로 표현하면 1<<col(4)이다.

따라서 첫 반복문의 i는 학번, 이름, 전공, 학년의 조합을 나타내게 된다.

예시
1000 -> 학번
0100 -> 이름
1100 -> 학번, 이름

 

유일성을 위한 중복성 체크로 set을 선언하고, 현재 조합 기준으로 가능한 값들을 키에 더해준다.

예시
1100 : 학번, 이름

K -> 1000 : 학번 (100, 200, 300, 400, 500, 600)
K -> 0100 : 이름 (ryan, apeach, tube, con, muzi, apeach)

Key = 100ryan, 200sapeach, 300tube, 400con, 500muzi, 600apeach

 

이렇게 구한 key 값을 더해주고, 해당 set의 크기가 튜플 총 개수 값과 같은 지 체크한다.

만약 다르다면 중복으로 인해 모든 튜플이 유일하게 식별되지 않는 다는 말이기에 유일성을 만족하지 못한 것이다.

 

이제 최소성을 체크할 변수를 선언해주자.

먼저 사전에 선언한 벡터 v를 통해 v의 값들을 모두 체크하며 (i&prev)=prev 식을 통해 현재 조합이 이전 조합에 포함되었는지 여부를 체크한다.

예시
i = 1100
prev = 0100

i&prev = 0100 -> 조합이 이미 있음
따라서 최소성 위반

 

이를 통해 최소성까지 통과한 값을 v에 담아주며, 최종적으로 v의 크기를 출력해주면 된다.