[프로그래머스] 후보키
문제 설명
프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다.
그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다.
/* 중략 */
릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하라.
제한사항
- relation은 2차원 문자열 배열이다.
- relation의 컬럼(column)의 길이는 1 이상 8 이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.
- relation의 로우(row)의 길이는 1 이상 20 이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.
- relation의 모든 문자열의 길이는 1 이상 8 이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.
- relation의 모든 튜플은 유일하게 식별 가능하다.(즉, 중복되는 튜플은 없다.)
풀이
60분 이상
우선 처음에 효율적인 코드를 짜겠다고 후보키에 포함되는 어트리뷰트를 지워가며 탐색했다. 예를들어 (1,2) 어트리뷰트가 후보키라면, 그 이상의 크기의 키들은 최소성을 만족하지 못하므로 1,2번 어트리뷰트를 제외하고 탐색하는 것이다. 하지만 코드를 짜다보니 다음 크기의 키를 탐색하면서 (2,3,4)어트리뷰트 집합이 후보키가 될 수 있다는 것을 깨닫고 지우는 과정을 없앴다. 그리고 나서도 한참을 통과하지 못했는데,
for(int size = 1; size <= col.size(); ++size){
comb(0, size);
}
위의 코드에서 size < col.size()라고 제한을 두는 바람에, 모든 어트리뷰트가 키가 되는 가능성을 배제해버렸다. 분명 문제를 풀기위해 고민하면서 생각해냈던 반례인데, 이 부분을 제대로 짚지 못하여 아쉬웠다. 그리고
for(int i : seq) temp += row[i];
위의 코드를 통해 후보키가 될 수 있는 어트리뷰트의 값들을 단순히 이어주면 문제가 발생할 수 있다고 생각했다.
[[“aa”,”a”],[“a”,”aa”],[“aa”,”aa”]]
이 경우에는 두 어트리뷰트를 모두 키로 사용할 경우 후보키가 될 수 있지만, 코드처럼 스트링을 이어버리면 첫번째 튜플과 두번째 튜플이 같다고 비교해버리게 된다. 이를 피하기 위해서 그냥 더해주는 것이 아니라 사이에 띄어쓰기를 추가해주기도 했는데, 그것을 다시 빼주어도 정상적으로 통과되는 것을 봐서는 상식적인(?) 테스트 케이스만 들어있는 것 같다.
코드
// 01:14 ~ ??
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>
using namespace std;
vector<int> col;
vector<int> seq;
vector<vector<int>> candidate;
vector<vector<string>> relation;
void iskey(){
set<string> s;
string temp;
for(vector<string> row : relation){
temp = "";
for(int i : seq) temp += row[i];
if(s.find(temp) != s.end()) return;
s.insert(temp);
}
for(vector<int> v : candidate){
int i;
for(i = 0 ; i < v.size(); ++i){
if(find(seq.begin(),seq.end(),v[i]) == seq.end()) break;
}
if(i == v.size()) return;
}
candidate.push_back(seq);
}
void comb(int idx, int size){
if(seq.size() == size){
iskey();
return;
}
for(int i = idx; i < col.size(); ++i){
seq.push_back(col[i]);
comb(i + 1, size);
seq.pop_back();
}
}
int solution(vector<vector<string>> _relation) {
relation = _relation;
for(int i =0;i< relation[0].size(); ++i) col.push_back(i);
for(int size = 1; size <= col.size(); ++size){
comb(0, size);
}
return candidate.size();
}