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

 

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

 

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

프로그래머스

---

 

 

해결전략

 

비트마스킹 Bit Masking

 

이 문제는 결국 풀지 못하고 다른 사람의 풀이를 봤다.

비트마스킹 방법을 사용하면 비교적 간단히 풀 수 있는 문제였다.

 

---

 

 

정답코드 - 비트마스킹 사용 

 

#include <iostream>
#include <string>
#include <vector>
#include <set>
using namespace std;

vector<int> candidate; // 후보 키

bool isUnique(int k) // 후보 키가 유일한지 확인하는 함수
{
    for (int i = 0; i < candidate.size(); i++) // 지금까지 찾은 후보 키를 모두 확인
    {
        // 현재 키 k가 기존 후보 키를 포함하고 있으면 유일하지 않음
		if ((k & candidate[i]) == candidate[i])
            return false;
    }

    return true; // 어떤 후보 키도 현재 키 k에 포함되지 않으면 유일함
}

int solution(vector<vector<string>> relation) {

    int row = relation.size();
    int col = relation[0].size();

    for (int i = 1; i < (1 << col); i++)
    {
        set<string> store; // 각 조합의 행을 저장할 셋

        for (int y = 0; y < row; y++)
        {
            string temp; // 열 값의 조합을 저장할 임시 문자열
            for (int x = 0; x < col; x++)
            {
                // i의 x번째 비트가 설정되어 있으면, 해당 열을 조합에 포함
	            if (i & (1 << x))
	            {
                    temp += relation[y][x]; // 열 값을 temp에 추가
	            }
            }
            store.insert(temp); // 조합을 store 셋에 삽입
        }

        if (store.size() == row) { // 모든 행이 이 열 조합에서 유일하면
	        if (isUnique(i)){ // 이 조합이 유일한지 확인
                candidate.push_back(i); // 조합을 후보 키 목록에 추가
	        }
        }
    }

    return candidate.size();
}

 

 

---

 

 

다른 방법의 풀이 참조

 

https://non-stop.tistory.com/650

 

 

---