[카카오 2019 문제] 후보키

 

분류

완전 탐색

혼자 힘으로 해결 했는가?

△ (엄청난 삽질을 해서 애매함)

느낀 점

 

이번 문제를 직접 모두 백트래킹으로 구현을 하려고 하니 너무 실수가 잦았다.

 

우선 각 칼럼마다 가능한 조합을 만들고 (백트래킹 + for문)

각 조합마다 다시 겹치는지 검사를 위해 다시한번 완전탐색을 사용하고 (2중 for)

만들어진 조합이 최소성을 충족하는지 따지기 위해 다시 백트래킹을 사용했다.

 

이렇게 구현을 하니 너무 힘이들었다. 이후 다른 분은 어떻게 해결했는지 참고했고

 

itertools와 set을 활용하는 인사이트를 얻을 수 있었다.

 

우선 각 칼럼마다 가능한 조합 자체를 itertools로 만들고 (물론 순수 백트래킹으로 만드는 방법도 알아야 한다고 생각한다.)

 

이후 하나의 칼럼의 조합이 유일성을 만족하는지 체크해야하는데, 이게 또 은근히 까다롭다.

 

1. 하나의 칼럼 조합에 맞도록 원본 배열을 재조합

이를 위해 참고한 블로그에서 아래와 같은 코드를 사용하셨다.

 

    for candi in candidates:
        tmp = [tuple([item[i] for i in candi]) for item in relation]
        if len(set(tmp)) == row:
            unique.append(candi)

 

여기서 파이썬의 컴프리핸션 문법도 잘 쓰면 유용하다는 것을 느꼈다.

 

tmp = [tuple([item[i] for i in candi]) for item in relation]

이 코드만 보면 처음에 이해가 가지 않았지만

 

컴프리헨션의 가장 기본적인 형태부터 다시 보면 이해가 가능하다.

 

[x * 2 for x in arr]

arr의 각 값들을 2배로만들어서 다시 배열로 만든다.

 

[tuple([item[i] for i in range(1,5,2)]) for item in arr]

2차원 배열 중 1,3 인덱스의 값만 뽑아내서 튜플이 담긴 하나의 리스트를 만든다.

 

이 문제를 해결할 때 가장 짜증이 났던 부분은 2차원 배열을 빠르게 각 행에서 특정 칼럼만 뽑아내는 것이었다.

 

그러나 저렇게 파이썬의 컴프리헨션으로 편하게 만들 수 있다는 것을 알고 앞으로 자주 연습을 해야겠다고 생각했다.

 

다음으로 그렇게 만들어진 새로운 테이블에서 각 행들이 유일한지 체크할 때, set을 이용하는 방법이 있다는 것을

놓치고 있었다. 1학년 때 파이썬 수업에서 리스트에서 중복을 제거할 때 set으로 만들고 다시 리스트로 만들었는데

그 방법을 사용할 수 있다는 것을 놓치고 그저 2중 for문으로 이상하게 중복을 체크했다.

 

원본의 2차원 배열에서 각 칼럼에 해당하는 값만 뽑아낸 후, 각 행들이 겹치는지 체크를 해야한다.

 

다음으로 역시 난감한 부분은 위의 과정으로 찾아낸 유일성을 만족하는 조합에 대해

각 조합끼리 포함이 되는지를 체크하는 부분이었다. 이 때도 집합을 이용한 유연한 사고를 하지 못했다.

 

하나의 조합이 다른 조합에 포함이 된다는 것은,

예를 들어 A가 B에 포함이 된다는 것은

 

A & B가 A이면 이는 A가 B에 포함이 되는 것이다.

 

즉 2개의 set에 대해 교집합을 구한 후 한쪽과 길이가 같다면, 이는 중복되는 집합이니 배제한다.

 

이 문제는 총 2가지 경우에 대한 인사이트를 얻을 수 있었던 문제였다.

---

 

참고한 코드 (https://whwl.tistory.com/104)

from itertools import combinations as combi

def solution(relation):
    row = len(relation)
    col = len(relation[0])

   
    candidates = []
    for i in range(1, col + 1):
        candidates.extend(combi(range(col), i))

 
    unique = []
    for candi in candidates:
        tmp = [tuple([item[i] for i in candi]) for item in relation]
        if len(set(tmp)) == row:
            unique.append(candi)

    answer = set(unique)
    for i in range(len(unique)):
        for j in range(i + 1, len(unique)):
            if len(unique[i]) == len(set(unique[i]) & set(unique[j])):
                answer.discard(unique[j])

    return len(answer)

 

 

 

---

비슷한 문제들