프로그래머스 42890 - 후보키 (c++)

프로그래머스 42890 - 후보키

문제 링크

생각 및 접근

• DB의 개념인 후보키의 갯수를 구하는 문제였다.

• 내 수도 코드는 이렇다.

  • 조합(dfs)을 통해서 칼럼의 갯수를 1부터 칼럼의 갯수까지 칼럼의 인덱스를 고른다.
  • 인덱스를 다 골랐다면, 기존에 후보키였던 것을 포함하는지 검사한다.
    • 기존에 후보키였던 것을 포함한다면, 지금 검사하는 칼럼의 인덱스는 최소성을 만족하지 못하므로 return
    • 기존에 후보키였던 것을 포함하지 않는다면,
      • vector<vector<string>> relation의 모든 레코드에 대해 칼럼의 인덱스의 값들을 추출해서, 한 vector<string>으로 잡는다. 잡은 vector<string>을 vector<vector<string>>에 넣는다.
      • 모두 넣고, 일일히 대조해서 처음부터 끝까지 일치하는지 확인한다.
        • 일치하는게 있다면, 후보키가 되지 못하므로 return
        • 일치하는게 없다면, 후보키가 될 수 있다.

• 조금 말이 어려운데, 코드를 보면서 이해해보자.

• 아래 코드는 후보키의 가짓수를 토대로 dfs를 돌리는 함수다.

    vector<vector<string>> rel;
  
    // answer는 후보키의 vector를 저장한다.
    vector<vector<int>> answer;
    int col, row, arr[21];
  
    int solution(vector<vector<string>> relation) {
        row = relation.size();
        col = relation[0].size();
        rel = relation;
  
        // i는 후보키의 가짓수
        for(int i = 1; i <= col; i++){
            // arr은 칼럼의 인덱스를 저장할 예정.
            memset(arr, 0, sizeof(arr));
            dfs(i, 0, -1);
        }
  
        return answer.size();
    }

• 아래 코드는 조합을 시행하는 dfs다.

    // 벡터 a와 벡터 b가 모두 같은 원소를 가지고 있는지 판단하는 함수다.
    bool vector_is_equal(vector<string> a, vector<string> b){
        int vec_size = a.size();
        for(int i = 0; i < vec_size; i++){
            if(a[i] != b[i])    return false;
        }
        return true;
    }
  
    // goal : 나는 인덱스를 goal개 만큼 집기로 했다.
    // cnt : 나는 인덱스를 cnt개 만큼 집었다.
    // idx : 나는 인덱스를 idx까지 골랐었다.
    void dfs(int goal, int cnt, int idx){
        // 조합을 통해 모두 집었다면,
        if(goal == cnt){
  
            // 기존에 찾아놓은 후보키를 포함하고 있는 지 검사
            for(auto i : answer){
                int ans_idx = 0;
                for(int j = 0; j < goal; j++){
                    if(i[ans_idx] == arr[j])    ans_idx++;
                    if(ans_idx >= i.size())     break;
                }
                if(ans_idx >= i.size()) return;
            }
  
            // 후보키가 될 수 있는지 검사할 예정
            // vector<vector<string>> relation에서 골라놓은 인덱스를 저장해놓은 arr에 존재하는 인덱스대로 하나의 tmp 벡터를 만들고, 이를 cmp 벡터에 넣어준다.
            vector<vector<string>> cmp;
            for(int i = 0; i < row; i++){
                vector<string> tmp;
                for(int j = 0; j < goal; j++)
                    tmp.push_back(rel[i][arr[j]]);
                cmp.push_back(tmp);
            }
  
            // 비교하는 과정
            for(int i = 0; i < row; i++){
                for(int j = i + 1; j < row; j++){
                    // 벡터가 하나라도 같은 게 있으면 후보키가 되지 못함
                    if(vector_is_equal(cmp[i], cmp[j]))  return;
                }
            }
  
            // 벡터가 모두 다르므로 후보키가 될 수 있다.
            vector<int> answer_temp;
            for(int i = 0; i < goal; i++)
                answer_temp.push_back(arr[i]);
            answer.push_back(answer_temp);
        }
  
        // 다음 조합 진행
        else {
            for(int i = idx + 1; i < col; i++){
                arr[cnt] = i;
                dfs(goal, cnt + 1, i);
            }
        }
    }

코드

#include <bits/stdc++.h>
using namespace std;

vector<vector<string>> rel;
vector<vector<int>> answer;
int col, row, arr[21];

bool vector_is_equal(vector<string> a, vector<string> b){
    int vec_size = a.size();
    for(int i = 0; i < vec_size; i++){
        if(a[i] != b[i])    return false;
    }
    return true;
}

void dfs(int goal, int cnt, int idx){
    if(goal == cnt){
        for(auto i : answer){
            int ans_idx = 0;
            for(int j = 0; j < goal; j++){
                if(i[ans_idx] == arr[j])    ans_idx++;
                if(ans_idx >= i.size())     break;
            }
            if(ans_idx >= i.size()) return;
        }

        vector<vector<string>> cmp;
        for(int i = 0; i < row; i++){
            vector<string> tmp;
            for(int j = 0; j < goal; j++)
                tmp.push_back(rel[i][arr[j]]);
            cmp.push_back(tmp);
        }

        for(int i = 0; i < row; i++){
            for(int j = i + 1; j < row; j++){
                if(vector_is_equal(cmp[i], cmp[j]))  return;
            }
        }

        vector<int> answer_temp;
        for(int i = 0; i < goal; i++)
            answer_temp.push_back(arr[i]);
        answer.push_back(answer_temp);
    }
    else {
        for(int i = idx + 1; i < col; i++){
            arr[cnt] = i;
            dfs(goal, cnt + 1, i);
        }
    }
}

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

    for(int i = 1; i <= col; i++){
        memset(arr, 0, sizeof(arr));
        dfs(i, 0, -1);
    }

    return answer.size();
}

채점 결과