Count Conforming Bit masks

이해가 쉽지 않은 문제여서 시간을 많이 썼다.

 

문제링크
https://app.codility.com/c/run/trainingU25PJT-GGA/

A: 00 0000 1111 0111 1101 1110 0000 1111(BIN) = 16,244,239
conforms to
B: 00 0000 1100 0110 1101 1110 0000 0001(BIN) = 13,032,961

 

여기서 conforms의 의미는 B가 A가 될 수 있다는 말이다.

 

B가 A가 된다?

다시 해석하면 '0은 0도 될 수 있고 1도 될 수 있겠고, 그러면 pow(2, n)을 사용해야겠구나' 라는 아이디를 떠올리자.

 

문제

def solution(A, B, C)

그런데 문제는 위와같이 A, B, C 세개가 주어지고 한번에 conforms 하는 경우 의 수를 구하라고한다.

대체 무슨말일까...

For example, for integers:
A = 11 1111 1111 1111 1111 1111 1001 1111(BIN) = 1,073,741,727,
B = 11 1111 1111 1111 1111 1111 0011 1111(BIN) = 1,073,741,631, and
C = 11 1111 1111 1111 1111 1111 0110 1111(BIN) = 1,073,741,679,

the function should return 8, since there are 8 unsigned 30-bit integers conforming to A, B or C, namely:
11 1111 1111 1111 1111 1111 0011 1111(BIN) = 1,073,741,631,
11 1111 1111 1111 1111 1111 0110 1111(BIN) = 1,073,741,679,
11 1111 1111 1111 1111 1111 0111 1111(BIN) = 1,073,741,695,
11 1111 1111 1111 1111 1111 1001 1111(BIN) = 1,073,741,727,
11 1111 1111 1111 1111 1111 1011 1111(BIN) = 1,073,741,759,
11 1111 1111 1111 1111 1111 1101 1111(BIN) = 1,073,741,791,
11 1111 1111 1111 1111 1111 1110 1111(BIN) = 1,073,741,807,
11 1111 1111 1111 1111 1111 1111 1111(BIN) = 1,073,741,823.

 

솔찍히 봐도 모르겠다...

 

아이디어

1. 이진수 0이 0 또는 1로 변할 수 있다고 했다.

2. 그러면 A의 총 경우의 수는 2^(0의개수)가 되겠다.

3. 이제 중학교 시절의 총 경우의 수를 구하는 생각을 해보자

A + B + C 에다가 -AB -BC -CA 를 해주고 마지막에 +ABC를 해주면 모든 경우의 수를 구할 수 있을 것이다.

 

풀이

def solution(A, B, C):
    a = bin(A)[2:]
    b = bin(B)[2:]
    c = bin(C)[2:]
    ab = bin(A|B)[2:]
    bc = bin(B|C)[2:]
    ca = bin(C|A)[2:]
    abc = bin(A|B|C)[2:]
    
    a_cnt = 0
    b_cnt = 0
    c_cnt = 0
    ab_cnt = 0
    bc_cnt = 0
    ca_cnt = 0
    abc_cnt = 0
    
    for i in a
        if i == '0':
            a_cnt += 1
    for i in b:
        if i == '0':
            b_cnt += 1
    for i in c:
        if i == '0':
            c_cnt += 1
    for i in ab:
        if i == '0':
            ab_cnt += 1
    for i in bc:
        if i == '0':
            bc_cnt += 1
    for i in ca:
        if i == '0':
            ca_cnt += 1
    for i in abc:
        if i == '0':
            abc_cnt += 1   
   
   return(pow(2, a_cnt)+pow(2, b_cnt)+pow(2, c_cnt) -pow(2, ab_cnt)-pow(2, bc_cnt)-pow(2, ca_cnt) +pow(2, abc_cnt))

 

리팩토링

def solution(A, B, C):
    def getCount(bi):
        cnt = 0
        for i in bi:
            if i == '0':
                cnt += 1
        return cnt

    a = bin(A)[2:]
    b = bin(B)[2:]
    c = bin(C)[2:]
    ab = bin(A|B)[2:]
    bc = bin(B|C)[2:]
    ca = bin(C|A)[2:]
    abc = bin(A|B|C)[2:]

    a_cnt = 0
    b_cnt = 0
    c_cnt = 0
    ab_cnt = 0
    bc_cnt = 0
    ca_cnt = 0
    abc_cnt = 0

    a_cnt = getCount(a)
    b_cnt = getCount(b)
    c_cnt = getCount(c)
    ab_cnt = getCount(ab)
    bc_cnt = getCount(bc)
    ca_cnt = getCount(ca)
    abc_cnt = getCount(abc) 

    return(
        pow(2, a_cnt) + pow(2, b_cnt) + pow(2, c_cnt)
        - pow(2, ab_cnt) - pow(2, bc_cnt) - pow(2, ca_cnt)
        + pow(2, abc_cnt))

 

그런데 위와같은 코드로 제출을 하면 50점밖에 맞지 못한다.

이유는 Long Input이 주어졌을때 bin(A)[2:]를 쓰면 문자열 자르기 때문에 성능이 떨어지기 때문이다.

 

a,b,c,ab,bc,ca,abc 선언부를 아래와같이 수정하면 100점이 나온다.

zfill은 이진수를 30자리로 맞추고 왼쪽의 빈 자리를 0으로 채우는 함수이다.

def solution(A, B, C):
    def getCount(bi):
        cnt = 0
        for i in bi:
            if i == '0':
                cnt += 1
        return cnt

    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)
    ca = format(C|A, 'b').zfill(30)
    abc = format(A|B|C, 'b').zfill(30)

    a_cnt = 0
    b_cnt = 0
    c_cnt = 0
    ab_cnt = 0
    bc_cnt = 0
    ca_cnt = 0
    abc_cnt = 0

    a_cnt = getCount(a)
    b_cnt = getCount(b)
    c_cnt = getCount(c)
    ab_cnt = getCount(ab)
    bc_cnt = getCount(bc)
    ca_cnt = getCount(ca)
    abc_cnt = getCount(abc) 

    return(
        pow(2, a_cnt) + pow(2, b_cnt) + pow(2, c_cnt)
        - pow(2, ab_cnt) - pow(2, bc_cnt) - pow(2, ca_cnt)
        + pow(2, abc_cnt))

 

 

감사합니다.