[프로그래머스] 후보키 - PYTHON

문제보기

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

 

풀이 & 코드

개인적으로 아쉬움이 많이 남는 문제다. 처음부터 충분히 더 잘 풀 수 있었는 데 너무 얼탔다. 한번 풀고 나서 다른 사람의 풀이들을 보고 인사이트를 얻어 다시 풀었다. 나같이 아직 부족한 사람들은 다른 사람의 풀이를 볼 수 있다는 점에서 백준보다 프로그래머스가 공부하기에 더 좋은 것 같다ㅎ 언젠가 고수가 되면 백준으로 넘어가야지...

 

후보키는 유일성과 최소성 두개를 판단해 주면 된다. 처음 풀 때의 인사이트는 다음과 같다.

유일성 : 해당하는 키의 column들을 모아 새로운 row들을 만들고 set를 이용해 중복 제거를 시켜준다. 새로운 row로 구성된 set와 원래 row랑 개수를 비교해 주면 된다. 만일 값이 같다면 중복 제거된 게 없었으니 유일성을 만족하는 것이고 같지 않다면 중복 제거가 일어난 것이기 때문에 유일성을 만족시키지 못한다!

최소성 : 필자는 bfs를 이용하여 길이가 긴 것 부터 짧은 거 순으로 유일성을 판단했다. 따라서 root는 모든 column들 이었고 last_leaf는 column 하나씩이다. 만약 특정 조합의 column들이 유일성을 만족하지 않는 다면 더 이상 깊이를 추가 하지 않았고, 특정 조합의 column들이 유일성을 만족하는 데 그것의 leaf들이 유일성을 만족하지 않는 다면, 해당 조합이 최소성과 유일성을 만족한다고 판단했다.

 

코드는 다음과 같다(정리가 되지 않아 많이 지저분하다..)

answer = []

def is_only(relation, lst):
    # 유일성 판단
    sum_relation = []
    for row in relation:
        str = ""
        for j in lst:
            str += row[j]
        sum_relation.append(str)

    return len(relation) == len(set(sum_relation))


def bfs(relation, lst):
	# 유일성을 만족하지 않으면 더 이상 깊이 추가x
    if is_only(relation, lst) == False:
        return False

	# 유일성을 만족하고 col 개수가 1이면 해당 col이 후보키
    if len(lst) == 1:
        answer.append("".join(map(str, lst)))
        return True

    flag = True
    for i, el in enumerate(lst):
        llst = lst[:]
        llst.remove(el)
        if bfs(relation, llst):
            flag = False
	
    # leaf에 후보키가 없다면 해당 lst가 후보키
    if flag:        
        answer.append("".join(map(str, lst)))

    return True


def solution(relation):
    bfs(relation, [i for i in range(len(relation[0]))])
    return len(set(answer))

 

코드가 사실 깔끔하지 않다. 또한 코드를 돌려보면 하면 하나의 후보키를 다양한 경로를 통해 여러번 찾는다. 다시 말해 무의미하게 리소스가 낭비된다. 이를 위해 중간에 조건문을 걸어 제거하는 방법도 있지만 bfs자체가 좋은 접근이 아니라고 생각했다. 다른 사람들의 코드를 살펴보았는데 몇까지 인사이트를 얻을 수 있었다.

1. bit로 column을 표시할 수 있다. -> 사실 처음 문제 봤을 때 생각하긴 했는데 최대 컬럼의 개수를 20개로 잘못보고 2^20이면 수가 너무 커서 맞지 않는 다고 생각했다. 참고로 최대 컬럼의 개수는 8이다... (젠장)

2. column의 개수가 많아질 수록 column 최소개수부터 판단하는 것이 더 효율적이며 유일성보다 최소성을 먼저 판단하는 것이 더 효율적이다.

4. set(list)에서 list의 원소가 list라면 mutable해 unhashable로 인해 에러가 나지만 tuple이라면 immutable해 hashable하기 때문에 에러가 나지 않다. 즉 2차원배열을 str로 바꾸지 않고 tuple로 바꾸어도 set으로 만들 수 있다.

 

4번에 대한 추가적인 설명을 하자면 list, dict같은 mutable들은 해당 주소 a에 값을 저장하지 않고 다른 곳 b에 저장해 b를 a에 바인딩을 해준다. 따라서 b가 아닌 다른 주소를 바인딩 하면 값을 변화시킬 수 있어 mutable이다. 하지만 int, float, str, tuple과 같은 immutable은 해당 주소에 값을 바로 저장해 값을 변화시킬 수 없다. 따라서 immutable이다. 보다 자세한 설명을 원한다면 해당 주소를 참고 바란다!

 

https://wikidocs.net/91520

03) Immutable과 Mutable

 

 

다시 짠 코드는 다음과 같다. 설명을 덧붙이자면 최소성은 해당 bit와 answer에 들어있는 값과 and 연산자를 사용해 판단하였다. 유일성 파트에서 col_list은 bit 값을 다시 column의 index들의 list로 바꾼 값이고, selected_col은 col_list와 relation을 이용해 새로운 row를 만들었고 set로 바꾸어주었다.

def solution(relation):
    answer = []
    n_col = len(relation[0])
    for bit in range(1, 2**n_col):
        # 최소성 판단
        if len([1 for ans in answer if bit & ans == ans]) > 0:
            continue
            
        # 유일성 판단
        col_list = [i for i in range(n_col) if bit & (1 << i) > 0]
        new_row = set(tuple(row[i] for i in col_list) for row in relation)
        if len(relation) == len(new_row):
            answer.append(bit)
                      
    return len(answer)

 

아이 깔끔하다!