프로그래머스 / 비트마스킹 / 2개 이하로 다른 비트

문제

---

 

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

프로그래머스

 

입출력

---

 

 

해설

---

 

x가 양수일 때, x와 비트가 1 ~ 2개 다른 수 중 제일 작은 수를 구하여라.

 

문제를 보고 접근을 "제일 작은 수"에 초점을 맞춰서 생각을 해보자.

그럼 다음 표와 같이 생각할 수 있다.

x	smallest_bigger_number
0	1
1	2
...	...
10^15	10^15 + 1

 

당연히 제일 작은 수는 하나 큰 수일 것이다.

하지만 문제에서는 비트가 1 ~ 2개만 달라야 한다고 한다.

그럼 0 -> 1, 1 -> 2이 된다. 어찌보면 + 1하는 수와 동일하다고 생각할 수 있다.

 

근데 7, 15와 같은 수는 어떨까?

1을 더하면 최상위 비트에서 한 칸 옆으로 움직이고, 하위 비트들은 다 0으로 꺼지게 된다.

그럼 문제에서 구하라는 1 ~ 2개만 바뀌는 결과가 되지 않는다.

 

문제에서 1 ~ 2개만 달라야 한다는 것에 초점을 맞춰보자.

7은 어떤 수가 돼야 할까?

문제에 정답이 나와있으므로 11인데, 왜 인지 생각해보자.

 

7 => 0b0111
11 => 0b1011

이다.

 

내가 1 ~ 2개만 달라야 하므로 최상위 비트의 1이 왼쪽에 있는 비트와 교대 된 결과를 볼 수 있다.

그럼 무조건 최상위 비트가 왼쪽 한 칸과 바뀌는 것이 제일 작은 수라고 할 수 있을까?

 

예를 들어 0b1001(9)이라는 수가 있다고 해보자.

제일 작은 수가 무엇일까?

정답은 0b1010(10)이 된다.

 

얼추 지금 규칙이 보이기 시작한다. 하나의 예시를 더 보자.

0b1010(10) -> 0b1100(12)

10이 12가 되었다.

 

위와 같은 예시로 우리는 이런 생각을 할 수 있다.

01 구간이 보일 때 10 으로 바꾸면 되겠다.

 

근데 맘대로 해당 구간을 설정하면 안 되고 제일 하위 비트에서부터 해당 구간을 찾아주면 된다.

고로 for문을 통하여 01 구간을 찾아서 리턴해주자.

정답코드

---

'''
'25. 11. 8.(토)

1. x > 0, x와 비트가 1 ~ 2개 다른 수 중 제일 작은 수

일단 제일 작은 수이려면 하나 더 큰 수이면 된다.
하지만 이랬을 경우 
7 -> 8
15 -> 16
이랬을 때 비트가 전부 바뀌므로 안된다.

1 ~ 2개만 바뀌려면 제일 뒤에 있는 비트 중에서
01인 구간을 찾고 두개만 바꿔주면 된다.
or 1을 더해주면 된다.
1. 제일 뒤에있는 비트가 0이면 켜주면 제일 작은 수
2. 제일 뒤에있는 비트가 1이면 처음으로 만나는 01 구간에서 바꿔주면 제일 작은 수.
'''
def findSmallestNumber(number: int) -> int:
    #1번 조건
    if number & 1 == 0:
        return number | 1
    
    #2번 조건
    for idx in range(1, 52):
        if not (number & (1 << idx)):
            return (number ^ (1 << idx)) & ~(1 << (idx - 1))

def solution(numbers):
    answer = []
    for num in numbers:
        insert_number = findSmallestNumber(num)
        answer.append(insert_number)
    return answer

 

깃허브 : https://buly.kr/31UAFeM

유튜브 :