[프로그래머스][KAKAO_BLIND][2019] 후보키

프로그래머스 코딩테스트 고득점 Kit의 문제입니다.

https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

코딩테스트 연습

 

문제

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

코딩테스트 연습 - 후보키

 

내가 작성한 코드

from itertools import combinations
from collections import defaultdict
import sys

def used_key(used, selected):
    for key in used:
        matched = 0
        for i in key:
            if i not in selected:
                break
            matched += 1
        if matched == len(key):
            return True
    return False

def solution(relation):
    answer = 0
    num_row = len(relation)
    num_col = len(relation[0])
    cols = [i for i in range(num_col)]
    used = []
    for r in range(1, num_col+1):
        for selected in combinations(cols, r):
            if used_key(used,selected):
                continue
            must_have_num_row = set()
            for row in relation:
                must_have_num_row.add(tuple([row[i] for i in selected]))
            if len(must_have_num_row) == num_row:
                used.append(selected)
                answer += 1

    return answer

• key의 길이가 짧은 순으로 "유일성" 확인
  • column의 조합
    - combination을 이용하여 len(column)까지 모두 뽑아 확인
  • 뽑은 column에 대해 모든 row의 값을 set에 append(must_have_num_row)
  • len(must_have_num_row) == num_row이면 유일성 만족
• 탐색하는 후보키가 이미 뽑은 후보키를 포함하면 탐색하지 않음 (최소성)
  
  • used_key
    - 찾은 키(used)가 현재 탐색할 키(selected)에 포함되면 True

 

다른 사람이 작성한 코드

from itertools import combinations

def find(candidate):
    keys = []
    for k in range(2, len(candidate)+1):
        for li in combinations(candidate, k):
            res = list(zip(*(i for i in li)))
            if len(set(res)) != len(res):
                continue
            for key in keys:
                if set(key).issubset(li):
                    break
            else:
                keys.append(set(li))
    return len(keys)

def solution(relation):
    answer = 0
    reverse = list(zip(*relation))
    candidate = []
    for col in reverse:
        if len(set(col)) == len(col):
            answer += 1
        else:
            candidate.append(col)
    answer += find(candidate)
    return answer

https://velog.io/@djagmlrhks3/Algorithm-Programmers-%ED%9B%84%EB%B3%B4%ED%82%A4-by-Python

[Algorithm] Programmers : 후보키 by Python

• tuple이나 set간의 포함관계 메서드가 있을거라 생각해서 찾아봤더니 역시 있었다
• in으로 확인될까 했는데, tuple이나 set는 원소 취급이 될 수 있으므로 안된다

 

기억해야할 것

• set 관련 메서드
  • issubset
    - subset이면 True
  • isdisjoint
    - 교집합이 없으면 True