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

내 코드 & 통과 시간

isValid = True
def solution(relation):
    cols = len(relation[0])
    rows = len(relation)
    
    combination = []
    def dfs(S, V, cnt, cols):
        if S == cols:
            if cnt:
                combination.append(V)
            return
        dfs(S+1, V+[S], cnt+1, cols)
        dfs(S+1, V, cnt, cols)
    
    dfs(0, [], 0, cols)
    unique = []
    for comb in combination:
        tmp = set()
        for idx in range(rows):
            newString = ""
            for jdx in comb:
                newString += relation[idx][jdx]
            tmp.add(newString)
        if len(tmp) == rows:
            unique.append(comb)
            
    minimality = []
    unique = sorted(unique, reverse=True)
    def dfs2(S, V, cnt, length, u):
        if S == length:
            if cnt:
                if V in unique:
                    if V != u:
                        global isValid
                        isValid = False
                        return
            return
        dfs2(S+1, V+[u[S]], cnt+1, length, u)
        dfs2(S+1, V, cnt, length, u) 

    answer = 0
    for idx in range(len(unique)):
        global isValid
        u = unique[idx]
        isValid = True
        dfs2(0, [], 0, len(u), u)
        if isValid:
            answer += 1
    return answer

14, 16, 18, 20, 21, 23은 gpt보다 빠름

GPT 코드 & 통과 시간

def solution(relation):
    rows = len(relation)
    cols = len(relation[0])
    
    # 가능한 모든 조합을 담을 리스트
    candidates = []
    
    # 모든 조합을 검사 (1부터 속성의 개수만큼)
    for i in range(1, 1 << cols):
        # 유일성 검사
        tmp = [tuple([relation[j][k] for k in range(cols) if i & (1 << k)]) for j in range(rows)]
        if len(set(tmp)) == rows:
            candidates.append(i)
            
    # 최소성 검사
    answer = set(candidates)
    for i in range(len(candidates)):
        for j in range(i+1, len(candidates)):
            # 이미 후보키로 선택된 속성의 부분집합이라면 제거
            if candidates[i] & candidates[j] == candidates[i]:
                answer.discard(candidates[j])
                
    return len(answer)

대부분이 나보다 빠름

풀이 방법

1. columns를 가지고 조합을 만든다.
    - gpt는 비트마스킹을 통해서 조합을 만들었다.

2. 만든 조합을 바탕으로 이 조합이 유일성 원칙을 지킬 수 있는지 확인한다.

3. 최소성 원칙을 지키기 위해서 한번 더 조합을 만든다.

    - gpt는 이번에도 비트마스킹을 통해서 해결했는데 조합을 구하진 않았다.

    - 만든 조합 중에 하나라도 유일성 리스트에 존재한다면 False => 최소성을 지키지 못했다.

4. 최소성을 지킨것을 리스트에 넣거나 answer를 1 더해준다.

느낀점

- 비트마스킹을 공부하자

- itertools 외우자

- 많이 풀어보자