카카오 블라인드 채용

[카카오] 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 카카오 블라인드 채용 후보키

admin

Recent Posts

2024년 11월 17일 일요일 – 서울 생활 129주차

괌여행 아내와 함께 괌으로 여행을 갔다. 출산 이후로 둘만 가는 첫 여행이다. 하와이가 일본인들이 많이…

3일 ago

2024년 11월 3일 일요일 – 서울 생활 127주차

반복적인 일상 매일 아침 일어나 회사에 출근하고, 저녁을 먹고 돌아오는 일상의 반복이다. 주말은 가족을 보러…

3주 ago

2024년 10월 6일 일요일 – 서울 생활 123주차

Planning A well-structured plan has the following characteristics:   First, the ultimate vision you aim to…

2개월 ago

2024년 9월 29일 일요일 – 서울 생활 122주차

English The most common problem for English learners like myself is that we often use…

2개월 ago

2024년 9월 22일 일요일 – 서울 생활 121주차

추석 추석을 맞아 친가 외가 처가 어르신들을 모두 뵙고 돌아왔다. 아이가 태어난지는 좀 됐지만 한국에서…

2개월 ago

2024년 9월 8일 일요일 – 서울 생활 119주차

주말 이번주는 아내가 올라와서 주말을 함께 보냈다. 둘만 밥도 먹고 뮤지컬도 보고, 모임도 나가고 집에서…

2개월 ago

This website uses cookies.