[Python] 프로그래머스 후보키

코딩테스트 연습 - 후보키

---

풀이

우선, 만약 relation이 학번, 이름, 전공, 학년으로 이루어져 있을 경우 각각에 인덱스를 주어 [0, 1, 2, 3]인 리스트를 생성하고 이를 사용해서 조합을 만들었습니다.

그다음 만든 조합을 문자열로 만들고 문자열로 바꾼 조합을 하나씩 가져와 키를 만들고 그 키가 후보키가 될 수 있는지 여부를 조사하게 했습니다.

그 후, 후보 키가 된다면 최소성에 의해 해당 후보키를 포함하는 조합을 지우는 작업을했고 후보키가 아니라면 해당 조합만 삭제하게 하여 해결했습니다.

---

코드

from itertools import combinations


def solution(relation):
    answer = 0

    temp = [i for i in range(len(relation[0]))]
    combi_lists = list()

    # 조합 생성
    for cnt in range(1, len(relation[0]) + 1):
        combi_lists.append(list(combinations(temp, cnt)))

    # 조합리스트를 문자열로 변경
    combi_str_list = list()
    for combi_list in combi_lists:
        for i in combi_list:
            combi_str_list.append(''.join(map(str, i)))

    while len(combi_str_list) > 0:
        candidate_key = list()
        is_candidate_key = True

        for r in relation:
            key = ""
            for j in combi_str_list[0]:
                key += r[int(j)]

            if key in candidate_key:
                is_candidate_key = False
                break
            else:
                candidate_key.append(key)

        if is_candidate_key is False:
            del combi_str_list[0]
            continue

        str_list = list(combi_str_list[0])

        combi_str_list = [s for s in combi_str_list if any(str not in s for str in str_list)]

        answer += 1

    return answer

---

pyo7410/Algorithm