이 포스팅에서는 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 |
AI AI Agent들이 어느 정도 유용한 건 맞지만, 생각보다 성능이 그렇게 시원찮은지는 모르겠다. 특히나 코드…
티앤미미 예약이 그렇게 힘들다는 티앤미미를 처남네가 운좋게 예약해서 어제 저녁 다녀왔다. 딤섬이 그렇게 맛있다고 하는데,…
아난티 부산 시설과 고객 서비스가 이렇게 극단적으로 다른 방향인 호텔이 있을까 싶다. 시설의 퀄리티는 5성급이라기에…
This website uses cookies.