[C++로 풀이] 후보키 ⭐⭐

Date:     Updated:

카테고리:

태그:

📌 후보키

난이도 ⭐⭐

🚀 문제

image

image


🚀 내 풀이 ⭕

#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}
  • 2️⃣ 해당 열의 조합이 후보키가 될 수 있는지 검사한다.
    1. 최소성 검사 👉 해당 열의 조합이 이미 후보키를 포함하면 이 열의 조합은 후보키가 될 수 없다.
    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️⃣ 유일성 검사

image

예를 들어 (이름, 전공) 조합의 유일성을 검사해본다면, “이름” 열에서 값이 같은건 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 이상일 때는 값이 같은 행이 있어도 희망이 있다. 조합 내의 다음 열에서 값이 다른 행 하나라도 있으면 된다.
    • 조합 내의 모든 열에서도 값이 같다면 유일성 위반.


🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기

댓글 남기기