[2019 카카오] 후보키

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

프로그래머스

카카오는 순열, 조합 문제를 좋아하는 것 같다.

아직 이런 유형의 문제가 약해서 ㅠ_ㅠ 이 문제도 앞쪽 문제인데 푸는데 한참 걸렸다.

백준에서 비슷한 유형을 많이 풀어봐야겠다!

 

모든 가능한 속성의 조합을 구하기 위해 비트연산자를 사용했다.

배열 v는 후보키가 될 수 있는 비트 상태를 저장하는 배열로,

배열 v에 속성 조합의 부분집합이 들어있는지 검사하는 함수로 exist 함수를 만들었다

(존재하면 1, 없으면 0)

exist 안에서 비트를 검사하는 식은 원래 내가 짰던 건 더 복잡했는데 다른 분께 깔끔해서 참고했다 T_T

 

그리고 비트를 읽어서 비트가 1인 속성의 번호를 저장하는 col_no 배열을 만들었다.

 

중복여부를 검사할때도 원래는 2중 포문을 선언해서 모든 튜플 쌍들에 대해 검사하는 방식으로 코드를 짰었는데

set을 이용하니까 매우 간단해졌다!

 

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

using namespace std;

// v에 부분집합이 존재하는지 검사하는 함수
bool exist(vector<int> &v, int flag) {
	for (int vv : v) {
		if ((flag & vv) == vv) return 1;
	}
	return 0;
}

int solution(vector<vector<string>> relation) {
	int answer = 0;
	int col = relation[0].size();
	int row = relation.size();
	vector<int> v;

	for (int i = 1; i < (1 << col); i++) {
		if (exist(v, i)) continue;

		vector<int> col_no;   // 1인 비트 번호 모음
		for (int j = 0; j < col; j++) {
			if (i & (1 << j))
				col_no.push_back(j);
		}

		set<vector<string>> s;

		for (int j = 0; j < row; j++) {
			vector<string> temp;
			for (int no : col_no) {
				temp.push_back(relation[j][no]);
			}
			s.insert(temp);
		}

		if (s.size() == row) v.push_back(i);
	}

	answer = v.size();

	return answer;
}