업데이트:

1 분 소요

문제

https://programmers.co.kr/learn/courses/30/lessons/42890

P_42890.png

풀이

먼저 주어진 릴레이션의 유일성과 최소성을 쉽게 확인하기 위해 사람 별 정보가 아닌 속성 별 정보로 나눈다.

이후 어떤 속성끼리의 조합이 유일성을 만족시키는지 알아내기 위해 각 속성의 index를 itertools.combinations를 통해 조합을 뽑아내고 zip을 통해 실제 데이터를 속성에 맞게 묶어준다.
묶어준 데이터들에서 중복이 있는지 확인하기 위해 set으로 변환했을 때 길이를 확인하여 그 차이를 확인해 count를 1올려준다.

조합을 구할 때는 1개 조합 부터 모든 조합을 차례로 구해가면서 최소성을 만족시킬 수 있는데, 이 때 전에 구해놓은 후보군(속성들의 인덱스 조합)이 현재 조합의 부분 집합인지 issubset함수를 사용 해 확인한 후 부분 집합이라면 반복문을 빠져나간다.

조합을 구하는 과정에서, 전체 집합이 후보키가 되는 경우를 고려하여 후보군의 길이 만큼 반복문을 진행해야 한다는 점을 주의해야 한다.

def solution(relation):
    from itertools import combinations
    answer = 0
    n = len(relation)
    rel = [[] for _ in range(len(relation[0]))]
    cand = [i for i in range(len(rel))]
    cand_chk = set()
    
    for r in relation:
        for i in range(len(r)):
            rel[i].append(r[i])
    
    for i in range(1,len(cand)+1):

        for comb in combinations(cand,i):
            switch = False
            
            for chk in cand_chk:
                if set(chk).issubset(comb):
                    switch = True
                    break
            if switch:
                switch = False
                continue

            tmp = []
            for j in comb:
                if j in cand_chk:
                    break
                tmp.append(rel[j])
            lst = []
            for chk in zip(*tmp):
                lst.append(chk)
            
            if len(set(lst)) == len(lst):
                cand_chk.add(comb)
                answer+=1

    return answer

생각 & 정리

그리 어렵지 않은 문제일 것으로 예상했는데, 전체 집합을 고려하지 않는 등의 문제로 많은 시간이 걸렸다.
카카오 블라인드 채용 문제라서 어려웠겠지라고 위안은 삼지만 이런 문제 또한 쉽게 풀어나가는 사람이 분명히 있기 때문에 더욱 노력해야겠다는 생각이 들었다.

댓글남기기