프로그래머스 42890 후보키 파이썬 풀이

난이도 : Lv. 2

풀이일 : 2501061

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

프로그래머스

---

문제

---

아이디어

• 주어진 입력에서 만들 수 있는 모든 컬럼 조합 추출 ([0], [1], [0, 1])
• 각 릴레이션의 저장된 컬럼들을 묶어 set에 저장 (("100"), ("200"))
• set의 길이와 릴레이션 총 길이가 같다면, 후보키가 될 수 있는지 검사
• 이미 저장된 후보키가 현재 구한 컬럼조합의 부분집합에 해당하는지 확인 후 후보키 여부 결정
• 후보키의 개수 출력

---

풀이 코드

def solution(relation):
    answer = 0
    all = []
    candkey = []
    
    def makenums(now, start, depth, nums, visited, array): # 모든 조합 방법 찾기
        if depth == len(nums):
            array.append(now)
            return
        
        for i in range(start, len(nums)):
            if not visited[i]:
                visited[i] = True
                makenums(now + [nums[i]], i, depth + 1, nums, visited, array)
                makenums(now, i, depth + 1, nums, visited, array)
                visited[i] = False
                
        array.sort(key=len) # 길이 기준 정렬
        return 

    makenums([], 0, 0, [i for i in range(len(relation[0]))], [False] * len(relation[0]), all)

    for i in range(1, len(all)): # [0], [0, 1], [0, 2], [0, 3], ...
        check = set()
        
        flag = True # 최소성 검사
        temp = []
        makenums([], 0, 0, all[i], [False] * len(all[i]), temp)
        for t in temp:
            if t in candkey:
                flag = False
        
        if flag:
            for j in range(len(relation)): # ["100", "ryan", "music", "2"], ...
                word = []
                for k in all[i]: # 0, 1, ...
                    word.append(relation[j][k])
                check.add(tuple(word))
            if len(check) == len(relation): # set 개수가 relation 길이와 같으면 후보키
                candkey.append(all[i])
    
    return len(candkey)

• makenums : 각 컬럼으로 만들 수 있는 모든 조합 추출
• all : 주어진 컬럼들로 만들 수 있는 모든 조합
• temp : 현재 컬럼들로 만들 수 있는 모든 조합
• flag : 최소성 확인 변수

---

제출 결과

---

느낀점

• 너무 느려서 어디 고칠 데 없나 더 노려보고 있어야겠다.
• 파이썬 코드 마음에 들게 고치면 자바로도 풀어봐야지