[카카오] 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 |