[프로그래머스] 후보키

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 이해 및 접근

후보키의 조합을 구해야하므로 조합을 구하는 모듈을 사용했습니다.

유일성과 최소성을 확인하기 위하여 집합을 사용하였습니다.

2) 알고리즘

• 조합

3) 풀이 코드

사용 언어 - Python

from itertools import combinations                  # 조합 구하기 위한 모듈 임포트

def solution(relation):         
    R = len(relation)                               # DB 행의 개수
    C = len(relation[0])                            # DB 열의 개수
    cols = set()                                    # 유일성과 최소성을 만족하는 후보키 목록

    for i in range(1, C+1):                         # 열이 선택되는 개수
        combs = list(combinations(range(C), i))     # 열이 i개 선택했을때 나오는 모든 조합들

        for comb in combs:                          # 조합 하나씩 확인
            data = set()                            # 각 열의 후보키 값들을 저장할 변수 (집합을 이용해서 겹치는 경우 저장 안되게 사용)

            for e in relation:                      # 각 행별로 데이터 확인을 위한 반복
                tmp = []                            # 후부키의 값들을 담은 임시 리스트 변수
                for i in comb:                      # 조합에서 선택된 열만큼 반복
                    tmp.append(e[i])                # 각 열의 값을 임시변수에 저장
                data.add(tuple(tmp))                # 후보키 값들 저장
            
            if len(data) == R:                      # 모든 후보키 값들이 유일성을 만족하면
                for col in cols:                    # 이전 정답의 후보키 설정 열의 목록 확인
                    if not (set(col) - set(comb)):  # 최소성 확인
                        break
                else:                               # 최소성도 만족하면 답에 추가
                    cols.add(comb)


    return len(cols)

---

📝 결과 및 학습한 내용

1) 어려웠던 내용

최소성의 조건을 만족하는 조합을 구하는데 어려움을 겪었습니다.

 

최소성을 검사하는 로직에 문제가 있었습니다.

후보키 만족시킨 열을 바로 제거하여 다음에 못사용하도록 하는 로직에 문제가 있어, 사용한 후보키 목록을 따로 정리하여 최소성 검사를 다시 실시하여 문제를 해결했습니다.

2) 새롭게 학습한 내용

특별히 없습니다.

---

🔗 문제 링크

- https://programmers.co.kr/learn/courses/30/lessons/42890?language=python3# 

코딩테스트 연습 - 후보키

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다