[19회차] 후보키, 2개 이하로 다른 비트

Programmers Level.2 후보키

from itertools import combinations

def solution(relation):
    answer_list = []
    num_list = []
    row = len(relation) # 튜플 개수
    column = len(relation[0]) # 속성 개수
    for i in range(column):
        num_list.append(i)
    for i in range(1, column + 1):
        for j in combinations(num_list, i): # 조합
            array = [[] for _ in range(row)]
            for k in range(row):
                for l in j:
                    array[k].append(relation[k][l])
                array[k] = tuple(array[k])
            if len(set(array)) == row:
                answer_list.append(j)
    print(answer_list)
    return
    
    
    # answer_list = [(0,), (0, 1), (0, 2), (0, 3), (1, 2), (0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3), (0, 1, 2, 3)]

 - 유일성을 찾는 것 까지는 해낼 수 있었다.

 - 하지만 최소성을 만족시키는 해를 찾기는 어려웠다.

 - 최소성을 만족시키는 해를 하나 찾았다면 이 해를 포함하는 나머지 해들은 최소성이 만족되지 않는 것은 알겠는데 이것을 어떻게 구현할 지는 아이디어가 떠오르지 않았고 오랜 고민 끝에 구글 검색을 통해 해결하기로 결정했다.

 

from itertools import combinations

def solution(relation):
    answer_list = []
    num_list = []
    row = len(relation) # 튜플 개수
    column = len(relation[0]) # 속성 개수
    for i in range(column): # num_list = [0,1,2,3]
        num_list.append(i)
    for i in range(1, column + 1): # i는 조합에 쓰이는 변수
        for j in combinations(num_list, i): # j는 조합
            array = [[] for _ in range(row)]
            for k in range(row):
                for l in j:
                    array[k].append(relation[k][l])
                array[k] = tuple(array[k])
            if len(set(array)) == row: # 유일성 판단
                put = True
                for x in answer_list:
                    if set(x).issubset(set(j)): # 최소성 판단
                        put = False
                        break
                if put: answer_list.append(j)
    return len(answer_list)

 

 

Programmers Level.2 2개 이하로 다른 비트

def solution(numbers):
    answer = []
    for number in numbers:
        if number % 2 == 0: # 짝수의 경우
            answer.append(number + 1) # 1만 더하면 됨
        else: # 홀수일 경우
            number = bin(number)
            number = number[0] + number[2:]
            i = len(number) - 1
            while True:
                if number[i] == '0': # 이진수로 표현했을 때 맨 오른쪽에 등장하는 0과 그 우측의 1을 자리 바꿈
                    number = number[:i] + number[i+1] + number[i] + number[i+2:]
                    answer.append(int(number,2))
                    break
                i -= 1
    return answer

 - 짝수는 이진수로 표현했을 때 마지막 자리 수가 0이므로 단순히 1만 더하면 해결.

 - 홀수일 때는 규칙을 찾아보니까 이진수로 표현했을 때, 맨 오른쪽에 등장하는 0과 그 우측의 1을 자리바꿈하면 됐고 이를 구현함.