프로그래머스 레벨2 - 카카오 2019 후보키

문제 주소

programmers.co.kr/learn/courses/30/lessons/42890

코딩테스트 연습 - 후보키

내 풀이

from itertools import combinations
def solution(relation):
    answer = 0
    columns = [ i for i in range(len(relation[0]))]
    combi = 1
    answerElements = []
    while True:
    	# 종료조건 
        if len(columns) < combi:
            break
        # 후보 조합을 추리는 과정 - 최소성을 유지하지 못하는 것은 toBeDeleted에 넣음
        combiColumns = set(combinations(columns,combi))
        toBeDeleted = set()
        for candidate in combiColumns:
            for element in answerElements:
                if set(element).issubset(set(candidate)):
                    toBeDeleted.add(candidate)
        # 후보 조합에서 정답에 해당하는 것을 골라내는 과정
        for column in combiColumns - toBeDeleted:
            key=set()
            for row in relation: 
                candidates = tuple([row[i] for i in column])
                if candidates in key:
                    break
                key.add(candidates)
            else: 
                answer+=1
                answerElements.append(column)
        # 조합의 수를 증가
        combi+=1
    return answer

몇 번 실패한 다음에 풀었던 문제다. 부분집합인지 체크하는 부분에서 막혔었는데 issubset 이라는 집합 메소드로 해결했다. 다른 사람들 풀이도 살펴봤는데 나한테는 꽤 어려웠던 문제라 그런지 다른 사람들의 풀이는 잘 이해가 안되었다ㅠㅠ 이중 for문을 2번이나 쓰고, 계속 set으로 변환해 주는 작업을 하는게 내 풀이의 아쉬운 부분이다.

 

tuple이 생각보다 다루기 어렵다는걸 느꼈고, for-else문을 보기만 하다가 처음 사용해봐서 의미있었다.

 

set의 새로운 메서드들도 알게되었다. boolean 값 리턴

• isdisjoint() : 두 집합이 공통원소를 갖는지
• issubset() : 부분집합인지
• issuperset() : 확대집합인지

해당 내용 참고 블로그(집합과 관련된 내용정리) : withcoding.com/77