Codility CountConformingBitmasks

2진수로 표현된 A와 B, C를 준수(Comforms)할 수 있는 2진수들의 개수를 찾는 문제입니다.

여기서 준수(Comforms)할 수 있는 2진수라는 뜻은 A라는 2진수의 0에 해당하는 자리가 0 또는 1이 될 수 있는 모든 수 입니다.

말이 어려운데, 예를 하나 들어보겠습니다.

1101

라는 수가 주어졌을 때,

1101
1111

이렇게 2개가 될 수 있습니다.

2번째 자리에 있는 유일한 0의 자리에 0 또는 1이 되는 2진수가 준수(Comforms)할 수 있는 2진수가 되는 것이죠.

즉, 준수(Comforms)할 수 있는 2진수의 개수는 원본이 되는 수의 0의 개수에 따라 0 또는 1이라는 두가지 선택지가 있기 때문에

준수(Comforms)할 수 있는 2진수의 개수 = (0의 개수)² 가 됩니다. 

 

다시 문제로 돌아와서 A, B, C 2진수의 준수(Comforms)할 수 있는 2진수를 찾으라는 말은 A, B, C의 준수(Comforms)할 수 있는 2진수의 합집합의 개수를 구하라는 말입니다.

3개의 합집합을 구하는 공식은 아래와 같습니다.

(A u B u C) = (A+B+C) - ((A ^ B) + (B ^ C) + (A ^ C)) + (A ^ B ^ C)

 

여기서, A, B, C 각각의 준수(Comforms)할 수 있는 2진수의 개수는 구할 수 있겠지만,

A와 B 혹은 B와 C, A와C의 교집합은 어떻게 정의할 수 있을까요??

A와 B에 공통으로 들어가는 0의자리는 그대로 유지하고 A와 B중 1에 해당하는 수는 1로 만들어야 하므로

A와 B의 OR연산(|)을 수행하게되면, A와 B에 공통된 준수(Comforms)할 수 있는 2진수를 구할 수 있습니다.

A, B, C의 교집합은 A | B | C 으로 구할 수 있겠죠??

 

구현한 코드는 아래와 같습니다.

def solution(A, B, C):
    a = format(A, 'b').zfill(30)
    b = format(B, 'b').zfill(30)
    c = format(C, 'b').zfill(30)

    ab = format(A | B, 'b').zfill(30)
    bc = format(B | C, 'b').zfill(30)
    ac = format(A | C, 'b').zfill(30)

    abc = format(A | B | C, 'b').zfill(30)
    a_cnt = 0
    for u in range(len(a)):
        if a[u] == '0':
            a_cnt += 1

    b_cnt = 0
    for u in range(len(b)):
        if b[u] == '0':
            b_cnt += 1

    c_cnt = 0
    for u in range(len(c)):
        if c[u] == '0':
            c_cnt += 1

    ab_cnt = 0
    for u in range(len(ab)):
        if ab[u] == '0':
            ab_cnt += 1

    bc_cnt = 0
    for u in range(len(bc)):
        if bc[u] == '0':
            bc_cnt += 1

    ac_cnt = 0
    for u in range(len(ac)):
        if ac[u] == '0':
            ac_cnt += 1

    abc_cnt = 0
    for u in range(len(abc)):
        if abc[u] == '0':
            abc_cnt += 1

    answer = pow(2, a_cnt) + pow(2, b_cnt) + pow(2, c_cnt) - pow(2, ab_cnt) - pow(2, bc_cnt) - pow(2, ac_cnt) + pow(2, abc_cnt)
    return answer