[프로그래머스/파이썬] 후보키(42890) 풀이

---

• 프로그래머스 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 프로그래머스 코딩테스트 연습
• 문제 링크: 후보키(42890)
• 문제풀이 코드 GitHub 링크
• 풀이 언어: Python 3

풀이

문제

릴레이션에서 유일성과 최소성을 만족하는 후보키의 개수를 구하는 문제입니다.

• 유일성: 선택한 속성 조합으로 모든 튜플을 구분 가능
• 최소성: 후보키의 부분집합이 또 후보키면 안 됨

코드

def solution(relation):
    answer = 0

    combs = []
    for i in range(len(relation[0])):
        getComb(combs, [i], len(relation[0])-1)
        
    combs.sort(key=lambda x:len(x))
    candKeys = []

    for comb in combs:
        isTried = False
        for candKey in candKeys:
            cnt = 0
            for col in candKey:
                if col in comb: cnt+=1
            isTried = cnt == len(candKey)
            if isTried: break
        if isTried: continue
        
        if isUniqueComb(relation, comb): candKeys.append(comb)

    answer = len(candKeys)
    
    return answer

def getComb(origin, comb, last):
    origin.append(comb)
    for i in range(comb[-1] + 1, last+1):
       getComb(origin, comb+[i], last)

def isUniqueComb(relation, comb):
    rows = set()
    for row in relation:
        result = []
        for col in comb: result.append(row[col])
        result = tuple(result)
        if result in rows: return False
        rows.add(result)

    return True

print(solution([["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]]))

설명

전체 컬럼 조합을 크기 순으로 확인하면서:

• 이미 찾은 후보키의 상위집합이면 최소성 위반으로 제외
• 남은 조합에 대해 유일성 검사

를 수행합니다.

유일성 검사는 선택한 컬럼값을 튜플로 묶어 set에 넣어 중복 여부를 확인합니다.

---

• 프로그래머스 문제풀이 전체 목록 보기

---