[프로그래머스] 후보키

2019 카카오 채용 코딩 테스트 문제입니다.

코딩테스트 연습 - 후보키

문제 확인

 

데이터베이스의 후보키 특성 유일성, 최소성 특성을 사용하는 문제입니다.

set 컨테이너를 통해 유일성, bit 표현식을 통해 최소성을 검사할 수 있습니다.

 

풀이

 

bit 표현식을 통해 사용한 칼럼을 표시합니다.

0101 : 0, 2번째 칼럼을 사용, 0011 : 0, 1번째 칼럼 사용

따라서 사용하는 칼럼의 개수가 N개라면 비트 표현식은 총 (1 ~ 1<<N) : 00...0 ~ 11...1 가 됩니다.

 

현재 검사하는 bit 식이 이미 후보키로 등록된 bit 식과 연산을 하여 최소성을 구합니다.

(이미 등록된 bit & 현재 bit) == 이미 등록된 bit의 경우 유일성을 만족하지 못함을 이용하여 최소성을 알아낼 수 있습니다.

 

같은 row에 해당하는 string 데이터를 ' '로 구분하여 모두 연결하고 이를 set 컨테이너에 넣습니다. set 컨테이너는 중복을 허용하지 않기 때문에 모든 row를 set 컨테이너에 넣고 난 후 set,size() == row 개수를 만족하지 않으면 중복이 일어나서 유일성을 만족하지 못함을 알 수 있습니다.

 

set 컨테이너와 스트링을 합치는 작업은 많은 시간을 소모하기 때문에 유일성 보다 최소성을 먼저 검사하여 시간을 단축할 수 있습니다.

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <set>
using namespace std;
 
bool check(vector<int> &res, int bit) {//최소성
    for (auto t : res)
        if ((t & bit) == t)
            return true;
    return false;
}
 
int solution(vector<vector<string>> relation) {
    int m = relation.size(), n = relation[0].size();
    vector<int> res;
 
    for (int i = 1; i < (1 << n); ++i) {
        if (check(res, i)) continue;//최소성 확인
 
        set<string> st;//유일성 확인
        for (int j = 0; j < m; ++j) {
            string now;
            for (int k = 0, bit = 1 << k; bit <= i; bit <<= 1, ++k) {
                if (i&(bit))
                    now += relation[j][k] + ' ';
            }
            st.insert(now);
        }
        if (st.size() == m)
            res.push_back(i);
 
    }
 
    return res.size();
}

정확성 테스트

테스트 1 〉	통과 (0.02ms, 3.98MB)
테스트 2 〉	통과 (0.02ms, 3.96MB)
테스트 3 〉	통과 (0.02ms, 3.92MB)
테스트 4 〉	통과 (0.03ms, 3.96MB)
테스트 5 〉	통과 (0.03ms, 3.95MB)
테스트 6 〉	통과 (0.01ms, 3.96MB)
테스트 7 〉	통과 (0.02ms, 3.96MB)
테스트 8 〉	통과 (0.01ms, 3.98MB)
테스트 9 〉	통과 (0.03ms, 3.93MB)
테스트 10 〉	통과 (0.02ms, 3.93MB)
테스트 11 〉	통과 (0.06ms, 3.96MB)
테스트 12 〉	통과 (0.14ms, 3.82MB)
테스트 13 〉	통과 (0.06ms, 3.97MB)
테스트 14 〉	통과 (0.02ms, 3.97MB)
테스트 15 〉	통과 (0.02ms, 3.96MB)
테스트 16 〉	통과 (0.02ms, 3.79MB)
테스트 17 〉	통과 (0.02ms, 3.95MB)
테스트 18 〉	통과 (0.21ms, 3.96MB)
테스트 19 〉	통과 (0.18ms, 3.97MB)
테스트 20 〉	통과 (0.42ms, 3.97MB)
테스트 21 〉	통과 (1.07ms, 3.96MB)
테스트 22 〉	통과 (0.40ms, 3.97MB)
테스트 23 〉	통과 (0.02ms, 3.97MB)
테스트 24 〉	통과 (0.05ms, 3.96MB)
테스트 25 〉	통과 (0.28ms, 3.96MB)
테스트 26 〉	통과 (0.49ms, 3.97MB)
테스트 27 〉	통과 (0.05ms, 3.82MB)
테스트 28 〉	통과 (0.26ms, 3.95MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0