[카카오] 2019 KAKAO BLIND RECRUITMENT 1차 풀이 – 후보키

이 포스팅에서는 2019 카카오 블라인드 채용 1차 문제인 ‘오픈채팅방’ 문제를 해설합니다. 본 풀이에 대한 테스트는 https://programmers.co.kr/learn/courses/30/lessons/42890에서 수행하였으며 공식 풀이와 일치하지 않을 수 있습니다.

공식 풀이는 링크를 참조하시기 바랍니다.


후보키

출처 : 2019 KAKAO 블라인드 채용 온라인 1차
링크 : https://programmers.co.kr/learn/courses/30/lessons/42890
카테고리 : Bit manipulation,
난이도 : 쉬움


문제 설명

DB의 Row에 해당하는 Record들이 주어진다. Record에는 여러 Column들이 있는데 이 Column의 값들을 조합해 Row를 구별할 수 있는 Unique한 Key를 만들 수 있는 모든 Column의 조합의 가짓수를 출력한다.

이 때 조합의 크기는 가능한 최소로 유지해야한다. 가령 Column A와 B를 가지고 Unique한 Key를 만들 수 있을 때, 조합 ABC나 조합 ABD와 같은 케이스는 최소성에 위배되므로 허용되지 않는다.


문제 풀이

우선 가능한 모든 조합을 0 ~ 2^N – 1의 숫자로 표시한 후, 비트 표현식에서 존재하는 1의 갯수에 따라 분류한다.

비트 수가 적은 것부터 차례로 Unique Key를 만들 수 있는지 검증한 후에, 가능하다면 이 조합을 True로 마크하고 이 조합에서 파생되는 모든 조합들을 False로 마크한다.

True인 조합의 수를 출력한다.


정답 코드

def get_bit_counts(ranges):
    ret = {}
    for i in range(ranges):
        num, cnt = i, 0
        while num > 0:
            cnt += num % 2
            num //= 2
 
        if cnt not in ret:
            ret[cnt] = []
 
        ret[cnt].append(i)
    return ret
 
 
def is_unique(relation, state):
    lookup_idx = []
    cnt = 0
    while state > 0:
        if state % 2 == 1:
            lookup_idx.append(cnt)
        state //= 2
        cnt += 1
 
    candidates = set()
    for record in relation:
        candidates.add(“”.join([str(record[i]) for i in lookup_idx]))
    return len(candidates) == len(relation)
 
 
def apply_minimality(is_valid_key, state):
    for i in range(len(is_valid_key)):
        if i & state == state:
            is_valid_key[i] = False
    return
 
 
def solution(relation):
    row, col = len(relation), len(relation[0])
    # 가능한 모든 키 사용 조합의 수
    comb = 2 ** col
 
    # 해당 키 조합이 유효한지를 저장 (-1 : 미정, 0 : 불능, 1 : 유효)
    is_valid_key = [1* comb
    # 사용된 키의 수에 따라 키 조합을 분류함.
    bit_count = get_bit_counts(comb)
 
    # 적은 갯수의 키를 사용하는 것부터 차례대로 탐색
    for cnt in bit_count:
        # cnt 갯수의 키를 사용하는 키 조합들에 대해
        for state in bit_count[cnt]:
            # 아직 초기화 안되었고, 이것들만으로 unique한 키를 만들 수 있으면
            if is_valid_key[state] == 1 and is_unique(relation, state):
                # Minimality를 위해 이 키를 포함하는 다른 키 조합을 모두 비활성화
                apply_minimality(is_valid_key, state)
                is_valid_key[state] = True
            else:
                is_valid_key[state] = False
 
    # 유효한 키의 갯수를 리턴
    return sum(is_valid_key)
cs

Competition 카카오 블라인드 채용 후보키