이 포스팅에서는 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 |
출장 오랜만에 출장을 간다. 미국으로 가는 출장은 항상 힘들다. 비행시간은 10시간에서 12시간. 도착해서 시차 극복도…
건강검진 재작년 말인가 작년 1월이었나, 인생 최악의 건강검진 결과를 받고서 다짐했었다. 2025년 건강검진에서는 완벽한 검사결과를…
운동 계획 운동과 식단과 피부관리 동시에 하니 시너지가 엄청나다. 변화가 눈에 보일 정도로 빠르다보니, 성취감도…
This website uses cookies.
