알고리즘(C++) / 프로그래머스 level 2 : 후보키

level 2 : 후보키 

https://programmers.co.kr/learn/courses/30/lessons/42890?language=cpp 

코딩테스트 연습 - 후보키

 

코드

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

using namespace std;

vector<int> ans;

// 최소성 확인
bool possi(int now) {
    for (int i = 0; i < ans.size(); i++) {
        if ((ans[i] & now) == ans[i])// 1101 & 1000 = 1000, ans[i] < now 무조건
            return false;
    }
    return true;
}

int solution(vector<vector<string>> relation) {
    int answer = 0;

    //모든 부분 집합, 비트마스킹
    for (int i = 1; i < (1 << relation[0].size()); i++) {
        set<string> s;
        for (int j = 0; j < relation.size(); j++) {
            string now = "";
            //각 위치해 있는 값
            for (int k = 0; k < relation[0].size(); k++) {

                if (i & (1 << k))
                    now += relation[j][k];
            }
            s.insert(now);
        }
        
        if (s.size() == relation.size() && possi(i))
            ans.push_back(i);
    }

    return ans.size();
}

int main() {
    vector<vector<string>> relation = 
    { {"100", "ryan", "music", "2" }, 
        { "200", "apeach", "math", "2" }, 
        { "300", "tube", "computer", "3" }, 
        {"400", "con", "computer", "4"}, 
        { "500", "muzi", "music", "3"}, 
        { "600", "apeach", "music", "2" }};

    cout << solution(relation) << "\n";

    return 0;
}

 

설명

비트마스킹을 이용하여 모든 집합을 순회할 수 있다. (1~(1<<4)까지 순회한다.) 1<<4는 1을 왼쪽으로 4번 shift한 것이므로 10000(2) = 16(10)까지 나타내어 모든 집합을 순회한다. 집합은 {0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111}까지 나타내고 &연산자로 1 위치에 해당하는 값들만 얻어 'now'에 저장한다.

s(set)에 얻은 string now를 insert하여 s의 size가 학생수와 같고 중복되어있지 않다면 후보키가 될 수 있다.

여기서 now가 중복된다면(중복되는 튜플이 있다면) set의 size는 학생 수와 같지 않을 것이다 .

 

고찰

이번 문제는 level 2에서 가장 어려운 문제였던거 같다.

 

비트마스킹(bitmasking)은 2진수로 표현하는 특성을 이용하여 정수의 이진수 표현을 자료구조로 쓰는 기법이다. 비트마스크를 이용하면 빠른 수행시간, 간결한 코드, 적은 메모리 사용할 수 있다.

&, |, ^, ~, << 등 사용할 수 있고 집합을 쉽게 표현할 수 있다. 

비트마스크를 사용하는 방법도 알아놔야 이런 문제를 쉽게 접근하고 구현할 수 있을거 같다. 

 

 

참조

https://hochoon-dev.tistory.com/entry/%ED%94%84%EB%A1%9C%EB%9E%98%EB%A8%B8%EC%8A%A4-%ED%9B%84%EB%B3%B4%EA%B8%B0-c

비트마스킹 - https://travelbeeee.tistory.com/451