[프로그래머스] 후보키

✔️ 문제 링크

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

프로그래머스

---

✔️ 풀이

- 릴레이션(DB 테이블)이 주어지고, 후보키의 최대 개수를 구하는 문제이다.

- 후보키는 유일성과 최소성을 만족해야한다. 

- 유일성은 set을 활용하여 컬럼의 중복여부를 확인하는 방법으로 체크했다.

- 최소성은 후보키를 이루는 속성들의 부분 집합중 유일성을 만족하는 집합이 있는지 확인하는 방법으로 체크했다. 후보키를 이루는 속성들의 모든 부분 집합에서 유일성을 만족시키는 집합이 있다면, 최소성을 만족하지 못하는 것이다. 

- 따라서 먼저 속성들에 대한 후보키 부분집합을 찾고, 각 후보키 조합에 대한 부분집합을 찾아서 유일성과 최소성을 만족 시키는 후보키 부분집합의 개수를 카운트한다.

- 이 문제는 어떤 집합의 부분 집합을 구하고, 그 부분 집합의 부분 집합을 구하는 문제이다.

- 내가 푼 방식은 조합을 만들어가는 과정에서 모든 부분 집합을 확인하며 풀었다. 즉 조합의 조합을 구하면서 모든 경우를 다 체크해봤다. 컬럼의 개수는 1개~8개이므로 시간 복잡도 우려가 되지 않았다. 

- 이 문제는 부문집합을 구하는 문제이다. 따라서 비트마스킹을 사용하면 더 간단히 풀 수 있다. 

---

✔️ 문제 회고

- 부문집합을 만드는 과정에서 조합을 사용했다. 부분집합의 부분집합을 찾아야하므로, 조합의 조합을 구현해야했는데, 코드가 복잡해져서 구현과정이 힘들었다.

- 부분 집합을 모두 직접 구현하는 것은 매우 번거롭다. 소스 코드 1은 리팩토링을 최대한 했지만, 거의 100줄에 육박하는 길이를 보여준다. 코드가 길어지면 구현이 복잡해진다는 것을 다시 한 번 느꼈다. 

- 소스 코드 2는 비트마스킹을 사용한 풀이다. 비트 마스킹을 사용함으로써 부분집합을 for문 한 개로 손쉽게 구할 수 있는 것 뿐만 아니라 최소성 검사도 상당히 간단하게 할 수 있음을 알 수 있다. (자세한 설명은 아래에)

---

👨🏻‍💻 소스 코드 1 

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

vector<vector<string>> g_relation;
vector<int> v;
vector<int> v2;
int columCount;
int ret = 0;
int retFlag;

bool isUnique(vector<int> colums) { //유일성 검사함수
	bool check[10] = { false };

	for (int k : colums) {
		check[k] = true;
	}

	bool flag = true;
	set<string> s;

	for (int i = 0; i < g_relation.size(); i++) {
		string tmp = "";
		for (int j = 0; j < g_relation[i].size(); j++) {
			if (!check[j]) continue;
			tmp += g_relation[i][j];
		}

		if (s.count(tmp) == 1) {
			flag = false;
		}
		s.insert(tmp);
	}

	return flag;
}

void combination2(int cnt) { // 후보키를 이루는 속성들의 부분 집합을 찾는함수

	if (v2.size() == v.size()) return;

	if (v2.size() > 0) {
		if (isUnique(v2)) retFlag++;
	}

	for (int i = cnt; i < v.size(); i++) {
		v2.push_back(v[i]);
		combination2(i + 1);
		v2.pop_back();
	}

}

bool isMinimum() { //최소성 검사함수
	retFlag = 0;
	combination2(0);
	if (retFlag == 0)
		return true;
	else if (retFlag > 0)
		return false;
}

void combination(int cnt) { // 후보키 부분 집합을 찾는 함수

	if (v.size() > 0) {
		if (isUnique(v) && isMinimum()) { // 유일성 만족하는지 검사한다. 
			ret++;
		}
	}

	if (v.size() == columCount) return;

	for (int i = cnt; i < columCount; i++) {
		v.push_back(i);
		combination(i + 1);
		v.pop_back();
	}
}

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

	g_relation = relation;
	columCount = relation[0].size();
	combination(0);

	return ret;
}

 

👨🏻‍💻 소스 코드 2 (비트마스킹 활용)

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

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

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

	int rowCount = relation.size();
	int columCount = relation[0].size();
	vector<int> ret;

	//비트 마스킹으로 후보키가 될 수 있는 모든 부분 집합을 찾음
	for (int bit = 1; bit < (1 << columCount); bit++) {

		set<string> s;

		for (int i = 0; i < rowCount; i++) {
			string tmp = "";
			for (int j = 0; j < columCount; j++) {
				if ( bit&(1 << j) ) //만들어진 부분집합에 속성이 속한다면
					tmp += relation[i][j];
			}
			s.insert(tmp);
		}

		// 원소에 중복이 있는지 검사, 
		if (s.size() == rowCount && isMininum(ret, bit))
			ret.push_back(bit);
	}

	return ret.size();
}

 

📌 비트마스킹 풀이설명

- relation의 컬럼이 4개인 경우를 가정하고 설명하겠다. 

- 4개의 속성에 대한 모든 부분 집합은 for문을 통해 아래와 같이 간단히 구현할 수 있다.

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

int main() {
	for (int bit = 1; bit < (1 << 4); bit++) {
		cout << bitset<8>(bit) << endl;
	}
	return 0;
}

 

결과

- 자 이제 모든 부분 집합 즉, 후보키가 될 수 있는 모든 조합에 대해 유일성과 최소성 검사를 하면된다.

- 유일성 검사는 set을 사용하여 중복 검사를 하면 된다.

- 최소성 검사는 다음과 같이 하면 된다. 이제까지 구한 유일성과 최소성을 만족시키는 후보키들과 새롭게 검사하려는 후보키를 비교한다. 만약 이제까지 구한 후보키들이 검사하려는 후보키를 포함한다면, 현재 검사하려는 후보키는 최소성을 만족시키지 못하는 것을 알 수 있다. 

- 예를들어 0101은 (인덱스 0 기준) 1번째 속성과, 3번째 속성은 복합키이자 후보키이다. 만약 새롭게 검사하려는 후보키가 0111 이라고 해보자 이는 1,2,3 번째 속성 포함하는 복합키이다. 만약 이 복합키가 유일성을 만족시켰을때 우리는 최소성을 검사해야한다. 하지만 0101 이란 후보키가 존재한다. 따라서 0111은 최소성을 만족하지 못한다. 1번째, 3번째 키로만 유일성을 판단할 수 있기 때문이다. 

- 따라서 isMininum 함수를 통해 최소성 여부를 판단할 수 있다. 포함여부는 bit 연산 특성을 활용하면 된다. 

- 우리는 후보키가 될 수 있는 모든 조합을 1부터 구했다. 따라서 유일성과 최소성을 만족시키는 집합 ret에는 항상 최소성을 만족시키는 후보키들이 들어있을 것이다.