이 포스팅에서는 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 |
합격왕 우여곡절 끝에 드디어 합격왕에 광고를 붙였다. 서비스를 시작한지 무려 4년이 지나서야 드디어 광고를 시작하게…
반복적인 일상 매일 아침 일어나 회사에 출근하고, 저녁을 먹고 돌아오는 일상의 반복이다. 주말은 가족을 보러…
Planning A well-structured plan has the following characteristics: First, the ultimate vision you aim to…
English The most common problem for English learners like myself is that we often use…
This website uses cookies.