[프로그래머스][2019 KAKAO BLIND][C++] 후보키

문제

프로그래머스 KAKAO BLIND RECRUITMENT - 후보키 (Level 2)

코딩테스트 연습 - 후보키

 

---

문제 풀이

접근 방식

이 문제는 2019 카카오 블라인드 채용 1차 코딩테스트 3번 문제로,

주어진 릴레이션의 후보키의 개수를 구하는 문제였다.

이 문제의 정답률은 약 16%로, 지원자들이 다소 어려움을 겪었던 문제라고 한다.

 

후보키가 되기 위해서는 유일성과 최소성을 만족해야 한다.

우선, next_permutation을 활용하여 주어진 릴레이션의 모든 속성 값 조합을 만들어주었고,

이 조합이 유일성을 만족하는지 unordered_map을 활용하여 확인해주었다.

 

유일성을 만족하는 조합들에 대해서는 최소성을 만족하는지 확인해주었다.

최소성을 만족하는지는 3중 for문과 find를 사용하여 확인해주었다.

 

---

풀이 코드 - C++

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int solution(vector<vector<string>> relation) {
    int col = relation[0].size();
    int row = relation.size();
    int count = 1;
    vector<vector<int>> result;
    while(count <= col){
        vector<int> idx(col);
        for(int i = 0; i < count; i++){
            idx[col - i - 1] = 1;
        }
        // 조합 만들기
        do{
            vector<int> temp;
            for(int i = 0; i < col; i++){
                if(idx[i] == 1) temp.push_back(i);
            }
            
            // 유일성 체크
            int temp_len = temp.size();
            bool check = true;
            unordered_map<string, int> dic;
            for(int i = 0; i < row; i++){
                string a = "";
                for(int j = 0; j < temp_len; j++){
                    a += relation[i][temp[j]];
                }
                if(dic[a] == 1){
                    check = false;
                    break;
                }
                dic[a] = 1;
            }
            if(check){
                result.push_back(temp);
            }
        }while(next_permutation(idx.begin(), idx.end()));
        count++;
    }
    
    // 최소성 체크
    vector<vector<int>> answer;
    for(auto uniqueness : result){
        bool check2 = true;
        for(auto minimality : answer){
            int cnt = 0;
            for(int a : minimality){
                if(find(uniqueness.begin(),uniqueness.end(),a) != uniqueness.end())
                    cnt++;
            }
            if(cnt == minimality.size()){
                check2 = false;
                break;
            }
        }
        if(check2)
            answer.push_back(uniqueness);
    }
    
    return answer.size();
}

실행 결과

실행 결과 : 100.0