5.3 비트 뒤집기

문제 

어떤 정수가 주어졌을때 여러분은 이 정수의 비트 하나에 0에서 1로 바꿀 수 있다. 이때 1이 연속으로 나올 수 있는 가장 긴 길이를 구하는 코드를 작성하라. 

 

해결법

1. 연속된 0수열과 1수열의 길이를 표현하는 배열로 바꿔서 생각해보기 

11011101111을 오른쪽에서 왼쪽으로 읽으면 [0(0),4(1),1(0),3(1),1(0),2(1)]로 구성될 것이고 이 배열을 읽으면서 0수열이 1인 경우 인접한 1수열을 합치는 경우를 따져 보면 된다. 

INT_SIZE = 32

def getSequences(n):
    seq =[]
    searchingfor = 0
    counter = 0
    for i in range(INT_SIZE):
        if  n & 1 != searchingfor :
            seq.append(counter)
            searchingfor = ~searchingfor
            counter =0
        counter +=1
        n >>>= 1
    return seq

def findLongestSequences(seq):
    maxSeq = 1
    len_seq = len(seq)
    for i in range(0,len_seq,2):
        zero = seq[i]
        left = seq[i-1] if i-1 >= 0 else 0
        right = seq[i+1] if i+1 < len_seq else 0

        thisSeq = 0
        if zero ==1:
            thisSeq = left + right + 1
        elif zero >1 :
            thisSeq = 1 + max(left,right)
        else :
            thisSeq = max(left,right)
        maxSeq = max(maxSeq, thisSeq)
    return maxSeq


def Solution(n):
    if n == -1 :
        return INT_SIZE
    seq = getSequences(n)
    return findLongestSequences(seq)

python3 에서 Int는 unlimited size이기 때문에 우선 4bytes로 가정하고 크기를 32로 정했다. 

이경우에서 b는 비트수라고 했을때 TimeComplexity = O(b) , SpaceComplextity = O(b) 일것이다. 

 

어쩌피 모든 비트를 확인하기는 해야하므로 시간복잡도를 줄일 수는 없다. 

하지만 공간복잡도를 줄일 수 있는 방법이 있을것이다. 

 

2. 현재 1수열 길이와 바로 이전 1 수열길이만 저장하고 있다가 0 비트를 만났을때 다음비트가 1인지 0인지에 따른 처리를 해주는 방법

0을 만났을때 

- 다음 비트가 1이면 prev_length는 cur_length가 된다. 

- 다음 비트가 0이면 prev_length는 0 이다 ( 합칠 수 없으므로 )

INT_SIZE = 32
def Solution ( n ):
    if ~n == 0:
        return INT_SIZE

    cur = 0
    prev = 0
    max_length = 1
    while n > 0 :
        if n & 1 == 1 :
            cur +=1
        elif n & 1 == 0:
            prev = 0 if n & 2 == 0 else cur
            cur = 0
        max_length = max(max_length , cur + prev + 1)
        n >>>=1

    return max_length

이경우에서 b는 비트수라고 했을때 TimeComplexity = O(b) , SpaceComplextity = O(1) 일것이다.