Info

• 카카오 2019 블라인드 공채 1차 출제
• 정답률: 16%
• 문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42890
• 결과: 성공

내 풀이

from collections import deque


def solution(relation):
    n_rows, n_cols = len(relation), len(relation[0])
    q = deque([[i] for i in range(n_cols)])
    answer = 0

    uniques = []
    while q:
        indices = q.popleft()
        search = [tuple(row[i] for i in indices) for row in relation]
        if len(set(search)) == n_rows:
            uniques.append(indices)
        q.extend([indices + [add_i] for add_i in range(indices[-1] + 1, n_cols)])
    uniques = sorted(uniques, key=lambda x: len(x), reverse=True)
    answer = 0
    for i in range(len(uniques)):
        if sum([set(uniques[i] + smallsets) == set(uniques[i]) for smallsets in uniques[i + 1:] if
                i < len(uniques) - 1]) == 0:
            answer += 1
    return answer