[카카오] 2018블라인드채용 - 3번 문제(후보키)

문제 & 출처

[프로그래머스 링크]

코딩테스트 연습 - 후보키 | 프로그래머스

'19 카카오 코딩 테스트 (C++) - YouTube

 

풀이과정

 

(1) 규칙

 

관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.

1. 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
2. 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

 

위의 예를 설명하면, 학생의 인적사항 릴레이션에서 모든 학생은 각자 유일한 학번을 가지고 있다.

따라서 학번은 릴레이션의 후보 키가 될 수 있다.

그다음 이름에 대해서는 같은 이름(apeach)을 사용하는 학생이 있기 때문에, 이름은 후보 키가 될 수 없다.

그러나, 만약 [이름, 전공]을 함께 사용한다면 릴레이션의 모든 튜플을 유일하게 식별 가능하므로 후보 키가 될 수 있게 된다.

물론 [이름, 전공, 학년]을 함께 사용해도 릴레이션의 모든 튜플을 유일하게 식별할 수 있지만, 최소성을 만족하지 못하기 때문에 후보 키가 될 수 없다.

따라서, 위의 학생 인적사항의 후보키는 학번, [이름, 전공] 두 개가 된다.

 

 

bit를 사용, 각 Attribute(column)과 아래의 1을 비교하여 후보키를 찾습니다.

 

0000 (0)	X
0001 (1)	학번
0010 (2)	이름
0011 (3)	학번,이름
0100 (4)	전공
0101 (5)	학번,전공
0110 (6)	이름,전공
0111 (7)	학번,이름,전공
1000 (8)	학년
1001 (9)	학번,학년
1010 (10)	이름,학년
1011 (11)	학번,이름,학년
1100 (12)	전공,학년
1101 (13)	학번,전공,학년
1110 (14)	이름,전공,학년
1111 (15)	학번,이름,전공,학년

 

 

(2) 순서

 

1부터(i) Attribute의 길이(1 << Attribute길이) 까지, i 가 후보키를 만족하는지 검색합니다.

예를들어 i가 5(0101)이라면, 학번에 중복이 있는지 확인, 전공에 중복이 있는지 확인합니다.

 

후보키 조건을 만족한다면 Attribute의 i 값을 임시벡터에 push 합니다.

(유일성 체크를 하지 않으므로 0001과 0101 둘다 임시벡터에 들어가게 됩니다)

 

1이 많은 bit순서대로 내림차순 한 후, 임시벡터.front()(1이 제일 많은 bit) 와 임시벡터.back()(1이 제일 적은 bit) 를 비교하여

유일성을 만족하지 않는 후보키는 제거합니다.(0001이 후보키라면 0101을 제거합니다)

 

(3) 코드

	#include <string>
	#include <vector>
	#include <algorithm>
	using namespace std;
	int countBits(int n)
	{
	int ret = 0;
	while (n)
	{
	if (n & 1) ret++;
	n = n >> 1;
	}
	return ret;
	}
	bool cmp(int a, int b)
	{
	//켜진 비트를 카운트
	int x = countBits(a), y = countBits(b);
	return x > y;//내림차순 정렬
	}
	bool check(vector<vector<string>> relation, int low, int col, int subset)
	{
	for (int i = 0; i < low - 1; i++)
	{
	for (int j = i + 1; j < low; j++)
	{
	bool isSame = true;
	for (int k = 0; k < col; k++)
	{
	if ((subset & 1 << k) == 0) continue;//ex) k는 1, (0010 & 0001)로 이라면, 검색하려는 Attrit이 아니다
	if (relation[i][k] != relation[j][k])//col 한줄에 중복값이 있는지 확인
	{
	//유일성 포함, 최소성을 만족하므로
	isSame = false;
	break;
	}
	}
	if (isSame)
	{
	return false;
	}
	}
	}
	return true;
	}
	int solution(vector<vector<string>> relation)
	{
	int answer = 0;
	vector<int> candidates;//후보키
	int low = relation.size();
	int col = relation.front().size();
	//컬럼중, 후보키 찾는다
	for (int i = 1; i <= (1 << col); i++)//
	{
	if (check(relation, low, col, i))
	candidates.push_back(i);
	}
	sort(candidates.begin(), candidates.end(), cmp);
	while (!candidates.empty())
	{
	int n = candidates.back();//1의 갯수가 제일 적은값부터
	candidates.pop_back();
	answer++;
	//유일성 체크
	for (vector<int>::iterator it = candidates.begin(); it != candidates.end(); )
	{
	if ((n & *it) == n)
	it = candidates.erase(it);
	else it++;
	}
	}
	return answer;
	}

view raw 카카오_3번_후보키.cpp hosted with ❤ by GitHub

 

+ 더 짧고 깔끔한 코드를 발견하여 추가합니다.

[프로그래머스의 w*db , 홍*용 , 임*섭 , 여훈 , min**** Jeong 외 3 명 분의 코드]

	#include <bits/stdc++.h>
	using namespace std;
	bool possi(vector<int> &vec,int now){
	for(int i=0;i<vec.size();i++)
	if((vec[i]&now)==vec[i])return false;
	return true;
	}
	int solution(vector<vector<string>> relation) {
	int n=relation.size();
	int m=relation[0].size();
	vector<int> ans;
	for(int i=1;i<(1<<m);i++){
	set<string> s;
	for(int j=0;j<n;j++){
	string now="";
	for(int k=0;k<m;k++){
	if(i&(1<<k))now+=relation[j][k];
	}
	s.insert(now);
	}
	if(s.size()==n&&possi(ans,i))ans.push_back(i);
	}
	return ans.size();
	}

view raw 카카오_3번_후보키2.cpp hosted with ❤ by GitHub