프로그래머스 [후보 키]

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

🔗 문제 링크

---

문제 설명 📄

주어진 relation 테이블에서 유일성과 최소성을 만족하는 후보 키의 개수를 구해야 한다.

• 유일성: 후보 키로 선택된 컬럼 조합이 모든 행에서 서로 다른 값을 가져야 한다.
• 최소성: 이미 후보 키가 된 컬럼의 부분 집합이 다른 후보 키가 될 수 없다.

---

문제 접근 방식 💡

• 모든 컬럼 조합을 생성하고, 유일성과 최소성을 검사한다.
• 유일성 검사: 같은 조합이 존재하면 후보 키로 사용할 수 없음.
• 최소성 검사: 기존 후보 키에 포함된 조합이라면 새로운 후보 키가 될 수 없음.
• 후보 키의 개수를 구함.

---

Solution 💻

from itertools import combinations

def solution(relation):
    database = set()

    for j in range(1, len(relation[0]) + 1):
        for i in combinations(range(len(relation[0])), j):
            skip = False
            for d in database:
                if set(d).issubset(i):
                    skip = True
                    break
            if skip:
                continue
            
            col = set()
            flag = True
            for r in relation:
                temp = tuple(r[idx] for idx in i)

                if temp in col:
                    flag = False
                    break
                col.add(temp)
            
            if flag:
                database.add(i)
            
    return len(database)

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(2^n * m)
  • n개 컬럼에 대해 모든 조합(2^n)을 검사.
  • m개의 행에 대해 중복 체크 수행(O(m))
• 공간 복잡도: O(2^n)
  • 후보 키를 저장하는 database의 크기.