[C++로 풀이] 후보키 ⭐⭐
카테고리: Programmers
태그: Coding Test Algorithm
📌 후보키
난이도 ⭐⭐
🚀 문제
🚀 내 풀이 ⭕
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int solution(vector<vector<string>> relation) {
int answer = 0;
int numOfRow = relation.size();
int numOfCol = relation[0].size();
vector<string> candKey; // 후보키 모아 둠
vector<bool> comb(numOfCol); // 조합 구하는데 쓰일 bool 배열
vector<int> cols(numOfCol); // colums 인덱스 (조합 할 대상)
for (int i = 0; i < numOfCol; ++i)
cols[i] = i;
for (int r = 1; r <= numOfCol; ++r) {
fill(comb.begin(), comb.end(), true);
for (int i = 0; i < r; ++i)
comb[i] = false;
do {
// Column 조합 뽑기
string combCols = ""; // 이번에 뽑은 Column 조합(stirng으로 관리)
for (int i = 0; i < numOfCol; ++i)
if (!comb[i])
combCols += to_string(cols[i]);
// 최소성 검사
bool isMinimal = true;
if (!candKey.empty()) {
for (int i = 0; i < candKey.size(); ++i) {
int count = 0;
for (int j = 0; j < candKey[i].length(); ++j) {
if (combCols.find(candKey[i][j]) != string::npos)
count++;
}
if (count == candKey[i].length()) isMinimal = false;
}
}
if (isMinimal == false) continue;
// 유일성 검사
bool isUnique = true;
for (int i = 0; i < numOfRow - 1; ++i) {
for (int j = i + 1; j < numOfRow; ++j) {
if (relation[i][combCols[0] - '0'] == relation[j][combCols[0] - '0']) {
if (combCols.length() == 1){
isUnique = false;
break;
}
bool canDisc = false;
for (int k = 1; k < combCols.length(); ++k) {
if (relation[i][combCols[k] - '0'] != relation[j][combCols[k] - '0'])
canDisc = true;
}
if (!canDisc)
isUnique = false;
}
}
}
if (isUnique == false) continue;
// 후보키 찾음 (위 두 검사 통과)
candKey.push_back(combCols);
} while (next_permutation(comb.begin(), comb.end()));
}
answer = candKey.size();
return answer;
}
- 1️⃣ “열(Column)”끼리의 모든 조합을 구한다. (열은 최대 8개라 시간 초과날 일은 없다.)
- 예를 들어 열이 4개라면
cols의 초기 값은 {0,1,2,3} 이 되며, 이를 통해 조합을 뽑는다.r = 1: {0} {1} {2} {3}r = 2: {0, 1} {0, 2} {0, 3} {1, 2} {1, 3} {2, 3}r = 3: {0, 1, 2} {0, 1, 3} {0, 2, 3} {1, 2, 3}r = 4: {0, 1, 2, 3}
- 예를 들어 열이 4개라면
- 2️⃣ 해당 열의 조합이 후보키가 될 수 있는지 검사한다.
- 최소성 검사 👉 해당 열의 조합이 이미 후보키를 포함하면 이 열의 조합은 후보키가 될 수 없다.
- 유일성 검사 👉 해당 열의 조합으로 모든 튜플의 구별이 가능해야 한다.
- 3️⃣ 위 검사를 모두 통과했다면 후보키인 것이므로 해당 열의 조합을
candKey에 넣어 후보키로 등록.
열의 조합은 문자열 combCols 로 관리했다. {0, 1, 3} 의 조합은 “013”이 되게끔 하였다. combCols 문자열이 이번에 뽑은 열 조합이다. (next_permutation 으로 조합 구하는 방법)
난 이 문제가 왜 이리 복잡하고 어렵게 느껴졌는지 모르겠다.. 어려워.. 겨우 풀었다 ㅠㅠ 어쩌다 통과 됐는지도 잘 모르겠다 큐ㅠㅠㅋㅋ
1️⃣ 최소성 검사
해당 열의 조합에 후보키 조합이 모두 들어 있다면 해당 열의 조합은 후보키가 될 수 없다.
1 차 풀이 ❌
bool isMinimal = true;
if (!candKey.empty()) {
for (int i = 0; i < candKey.size(); ++i) {
if (combCols.find(candKey[i]) != string::npos) {
isMinimal = false;
break;
}
}
}
if (isMinimal == false) continue;
나는 열끼리의 조합을 combCols 문자열에 저장했다. “013” 이런 식으로. 후보키를 찾았다면 이 문자열 그대로 candKey에 넣어주었다. 이렇게 string의 find 를 사용했을 때의 문제점은 “0123” 조합에 “13” 후보키가 포함되는 것을 거를 수 없다는 것이다. 1과 3이 붙어 있지 않아서 find로부터 걸리지 못했지만 사실 (0, 1, 2, 3) 열 조합에 (1, 3) 후보키의 조합인 1, 3 이 모두 들어있어서 후보키가 될 수 없다.
2 차 풀이 ⭕
// 최소성 검사
bool isMinimal = true;
if (!candKey.empty()) {
for (int i = 0; i < candKey.size(); ++i) {
int count = 0;
for (int j = 0; j < candKey[i].length(); ++j) {
if (combCols.find(candKey[i][j]) != string::npos)
count++;
}
if (count == candKey[i].length()) isMinimal = false;
}
}
if (isMinimal == false) continue;
그래서 문자열을 포함하는지 말고 문자 하나하나 단위로 다 포함하는지를 따져서 해결하였다. cnadKey 후보키 문자열의 하나하나의 모든 문자가 모두 combCols에 포함되어 있다면 combCols는 후보키가 될 수없다.
2️⃣ 유일성 검사
예를 들어 (이름, 전공) 조합의 유일성을 검사해본다면, “이름” 열에서 값이 같은건 2 개의 apeach 뿐이다. 그러나 두 appeach의 전공은 다르기 때문에 결론적으로 (이름, 전공)만으로 모든 튜플을 구별할 수 있는 것이나 마찬가지이다. 이 경우 유일성을 가진다.
1 차 풀이 ❌
bool isUnique = true;
// 문자열 합치기
vector<string> addCols(numOfRow, "");
for (int i = 0; i < numOfRow; ++i)
for (int j = 0; j < combCols.length(); ++j)
addCols[i] += relation[i][combCols[j] - '0'];
// 나와 뒤에 것들 전부 비교 (a[0]과 a[1],a[2],a[3] 비교 / a[1]과 a[2], a[3] 비교 이런식)
for (int i = 0; i < numOfRow - 1; ++i) {
for (int j = i + 1; j < numOfRow; ++j) {
if (addCols[i] == addCols[j]) {
isUnique = false;
break;
}
}
}
if (isUnique == false) continue;
처음엔 위와 같이 유일성을 검사하였다. 예를 들어 combCols 가 “01” 이라면 addCols 벡터에 0 열과 1 열에 해당하는 값들을 문자열로서 붙여버린 문자열들을 저장했다. (addCols[0] = “100ryan”, addCols[0] = “200apeach” 이런 식으로!) 그리고 이 addCols 값이 모두 다른지를 따졌다. 하나라도 같다면 튜플 구별이 안된다는 것이니 유일성에 어긋난다고 판단했다.
x | xx
xx | x
근데 이 같은 풀이의 문제점은 위와 같이 실제론 구별이 가능하지만 합쳐버리면 둘 다 같은 값이 되버리는 경우 xxx 가 되버려서 유일성에 어긋난다고 잘못 판단된다는 것이다. 그래서 이렇게 단순히 해당 열 조합에 해당하는 값들 문자열로 다 합치고 비교하면 안된다.
2 차 풀이 ❌
bool areSameDFS(vector<vector<string>>& relation, string& combCols, bool isSame, int row1, int row2 ,int nextCol){
if (nextCol == combCols.length())
return isSame;
if (relation[row1][combCols[nextCol] - '0'] != relation[row2][combCols[nextCol] - '0'])
isSame = isSame && false;
else
isSame = isSame && true;
areSameDFS(relation, combCols, isSame, row1, row2, nextCol + 1);
}
// ...
bool isUnique = true;
for (int i = 0; i < numOfRow - 1; ++i) {
for (int j = i + 1; j < numOfRow; ++j) {
if (relation[i][combCols[0] - '0'] == relation[j][combCols[0] - '0']) {
if (areSameDFS(relation, combCols, true, i, j, 1) == true){
isUnique = false;
break;
}
}
}
if (isUnique == false) break;
}
if (isUnique == false) continue;
그래서 만약 값이 같다면 DFS 로 들어가서 다음 열 조합 중 값이 다른게 있는지 검사하는 식으로 짜보았다. 예를 들어 “023” 조합을 검사한다면 0 번째 열에서 같은 값을 가지는 행들이 있다면 그 행들의 다음 열 2 번째 열에서는 다른 값을 가지는지 보고 거기서도 같으면 또 3 번째 열로 가서 다른 값을 가지는지 보는 것이다. 다른 값을 가지는게 하나라도 있었다면 areSameDFS 함수는 false 를 리턴할 것이며 이는 유일성을 만족한다고 판단될 수 있다. 반면에 해당 열 조합에서 특정 행들이 모두 같은 값들을 가졌다면 areSameDFS 함수는 true 를 리턴하여 이는 유일성을 위반한다고 판단될 수 있다. 예를 들어 (이름, 전공) 열을 검사한다면 이름 열에서 appeach 로 같은 2, 6번째 행은 전공 열에서는 math, music으로 각각 다르므로 유일성을 만족한다. 반면 (이름, 학년) 열은 appeach 로 같은 2, 6번째 행이 학년 열에서는 2 와 2 로 같기 때문에 유일성을 만족하지 못한다. (이름, 학년)만으로 구별할 수 없는 튜플이 존재한다는 것이기 때문이다.
그러나 위 풀이는 프로그래머스에서 실행시키면 Core Dumped 에러가 발생했다. 비주얼 스튜디오나 여러 웹 컴파일러나 다른 IDE 에서 돌렸을 때는 에러가 발생하지 않고 문제가 전혀 없이 테스크 케이스들을 만족했는데 완전히 동일한 코드를 오직 프로그래머스에서 돌릴 때에만 에러가 났다. 진짜 이유를 모르겠다.. 진심 뭐지?.. 도대체 왜 프로그래머스에서만 에러가 날까? 정말 궁금한데 이유를 알아내지 못했다.
하는 수 없이 다른 풀이를 짜야 했다.
3 차 풀이 ⭕
// 유일성 검사
bool isUnique = true;
for (int i = 0; i < numOfRow - 1; ++i) {
for (int j = i + 1; j < numOfRow; ++j) {
if (relation[i][combCols[0] - '0'] == relation[j][combCols[0] - '0']) {
if (combCols.length() == 1){
isUnique = false;
break;
}
bool canDisc = false;
for (int k = 1; k < combCols.length(); ++k) {
if (relation[i][combCols[k] - '0'] != relation[j][combCols[k] - '0'])
canDisc = true;
}
if (!canDisc)
isUnique = false;
}
}
}
if (isUnique == false) continue;
- 열 조합의 길이가 1 일 때는 ({0} {1} 이런 것 처럼) 값이 같은 행 하나만 발견해도 유일성 위반이다.
- 열 조합의 길이가 2 이상일 때는 값이 같은 행이 있어도 희망이 있다. 조합 내의 다음 열에서 값이 다른 행 하나라도 있으면 된다.
- 조합 내의 모든 열에서도 값이 같다면 유일성 위반.
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기