[프로그래머스] 후보키

문제

문제

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

코딩테스트 연습 - 후보키

 

처음 작성한 코드

def solution(relation):
    from itertools import combinations
    tupleNum = len(relation)
    attributeNum = len(relation[0])
    relation = list(map(list, zip(*relation)))
    result = []
    for i in range(attributeNum):
        allCombi = combinations(range(attributeNum),i+1)
        for j in allCombi:
            tmp = []
            for k in j:
                tmp.append(relation[k])
            if len(set(zip(*tmp))) == tupleNum:
                for ret in result:
                    if set(ret).issubset(set(j)):
                        break
                else:
                    result.append(j)
    return len(result)

1. relation에 같은 열을 묶은 배열들을 저장한다. -> 예시에서 학번은 학번끼리, 이름은 이름끼리 이런식으로..
2. attribute수를 인덱스로 하여 가능한 모든 조합을 뽑아낸다. -> 0, 1, 2, 3 , (0,1), (0,2) .. 이런식으로
3. relation[k]로 접근을 하면 k가 0일땐 tmp에 학번을 모아둔 리스트가 저장이 된다. 조합이 0,1일때는 학번리스트와 이름 리스트가 저장이 된다.
4. zip(*tmp)를 통해 같은 열의 값들을 묶어주고 set으로 중복을 제거하여 기존의 tupleNum과 같아지면 유일성이 입증된다.
5. result에는 최소성을 만족하는 조합들이 들어가있는데 result에 현재 조합에서의 하나의 값이라도 들어가있으면.. 즉 만약 result에 0이 있고 현재 조합이 0,1 이라면 조합 중 하나의 값인 0이 result에 있기 때문에 if 절에 걸려 break가 되어 result에 append 되지 않을 것이다. 이런 방식으로 최소성을 입증한다.

 

깨달은 점

• zip()은 크기가 같은 리스트들에서 같은 인덱스에 있는 값들을 뽑아준다.

• zip(list1,list2,list3) 이렇게도 사용할 수 있지만 list1,list2,list3이 2차원 배열로 하나의 변수 a에 저장되어 있다면 zip(*a) 이렇게 사용할 수 있다. -> 같은 열에 있는 값들을 뽑아서 저장할 때 유용하다.

 

• python에서는 부분집합인지 아닌지를 체크해주는 함수인 issubset()이 있다. 

• a = {1,2,3}, b = {1} 일 때, b는 a의 부분집합이다. b is subset of a 의 의미로 b.issubset(a)라고 쓰면 True를 반환한다.

 

• python에는 for-else문이 존재한다.

• for문을 다 돌고 break가 되지 않으면 else 문으로 간다. 위 코드에서 보면 if 절에 걸려서 break가 안될 경우는, result가 빈 리스트거나 다 돌았는데 부분집합이 아니거나 로 둘 중 하나이다. 그러면 그때 else로 가서 append를 해주는 것이다.

---

• 로직상 어렵지않은 문제였는데 파이썬 문법을 잘 몰라서인지 시간이 오래걸렸다.. 문법을 모른다는건 핑계겠지? 푸헹~ 다시 짜라하면 못짤거같다 푸헹~~