[Python] 프로그래머스 LV.02 - 2개 이하로 다른 비트

https://programmers.co.kr/learn/courses/30/lessons/77885

코딩테스트 연습 - 2개 이하로 다른 비트

[ 알고리즘 ]

단순구현

 

[문제 접근]

문제가 어렵다기보단, 일일이 비교하면 시간초과가 나는 문제이다.

처음엔 1씩 더해서 각각의 이진수를 구하고, 끝자리부터 한자리씩 더해나가며 해결하려고 했으나

그렇게 되면 시간복잡도가 어마어마하게 커지게 된다.

 

이 문제는 짝수와 홀수를 나눠서 생각 할 필요가 있다.

 

(1) 짝수 case

짝수의 경우 2진법으로 바꾸면, 무조건 끝에 0이 오게되어있다.

1~2자리수만 다르면 되므로, 맨 끝에 0을 1로만 바꿔주면된다.

 

(2) 홀수 case

홀수의 경우 7=111 이런 경우를 대비하여, 맨 앞에 0을 먼저 넣어줬다.

그 다음, 끝에서부터 0인 부분을 찾아서 1로 바꿔주고, 끝에 바로 전의 숫자를 0으로 바꿔준다.

예를 들어,

7=0111 의 경우 0111 -> 1111 -> 1011 이렇게 바꿔주면 제일 작으면서 2자리수가 다른 비트가 나오게된다.

 

2진법을 10진법으로 바꿀 땐, int(수,2) 내장함수를 사용하였다.

 

[코드]

from collections import deque

# 2진수 구하기
def func(num):
    que = deque()
    while num > 1:
        ptr = num % 2
        num = num // 2
        que.appendleft(ptr)
    que.appendleft(num)
    return que

def solution(numbers):
    answer = []
    for num in numbers:
        ans = func(num)

        # 짝수일 때
        if num % 2 == 0:
            ans[-1] = 1
        else:
            if ans[0] == 1:
                ans.appendleft(0)
            # 제일 끝의 0 찾기
            for i in range(-1, -len(ans) - 1, -1):
                if ans[i] == 0:
                    ans[i] = 1
                    ans[i + 1] = 0
                    break

        answer.append(int(''.join(map(str,ans)), 2))

    return answer