[Algorithm] - Bit연산자 부분 집합

Bit 연산자

---

Bit연산자로 표현하는 방법을 나타보도록 하겠습니다.

 

프로그래머스 - 후보키 문제

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

프로그래머스

 

N이 어떤 집합의 원소 갯수라고 합니다.

특정 부분 집합에 대해 특정 원소가 들어간다 or 들어가지 않는다로 나누어집니다.

이를 원소 갯수만큼 반복하여 생각하면 됩니다.

 

만약 4가지를 경우의 수로 나타나고 싶다면 각 Index가 표현된 방법을 의미하여, 0001 - 1111로 나타날 수 있다.

그렇기 때문에 각 경우의 수에 관련된 Data 값은 & 연산자로 Data를 추가하여 주면된다.

i는 0001 ~ 1111 을 나타냈으며, k는 각 Index가 가진 값이 i에 해당되면 해당 값들을 추가 하도록 만든 것입니다.

 

코드

---

def solution(relation):
    for i in range(1, 1 << len(relation[0])):
        tmp_set = set()
        for j in range(len(relation)):
            tmp = ''
            for k in range(len(relation[0])):
                if i & (1 << k):
                    tmp += str(relation[j][k])
            tmp_set.add(tmp)

        print(i,tmp_set)

relation = [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]]
solution(relation)

# bit 연산자로 모든 경우의 수 나타내보기

#1 level = [ 'kakao' , 'line' , 'lg' , 'danal']
#2 level = [ 'chonsik' , 'ryan' , 'muzi' , 'moonu']
#3 level = [ '3000' , '4000'  , '5000' , '6000' ]

datas = ['kakao chonsik 5000' , 'line muzi 6000' , 'danal ryan 3000' ,'lg moonu 4000']
data = [data.split(' ') for data in datas ]
level = 3

for i in range(1, 1<<level) :
    temp = set()
    for j in range( len(data) ) :
        tmp = ''
        for k in range(len(data[0])):
            if i & (1<<k) :
                tmp += data[j][k]
        temp.add(tmp)
    print(i,temp)