99클럽 코테 스터디 2일차 TIL

[level 2] 2개 이하로 다른 비트 - 77885

문제 링크

성능 요약

메모리: 25.3 MB, 시간: 27.54 ms

구분

코딩테스트 연습 > 월간 코드 챌린지 시즌2

채점결과

정확성: 100.0
합계: 100.0 / 100.0

제출 일자

2024년 04월 14일 16:41:23

문제 설명

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.

• x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수

예를 들어,

• f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.

수	비트	다른 비트의 개수
2	000...0010
3	000...0011	1

• f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.

수	비트	다른 비트의 개수
7	000...0111
8	000...1000	4
9	000...1001	3
10	000...1010	3
11	000...1011	2

정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ numbers의 길이 ≤ 100,000
• 0 ≤ numbers의 모든 수 ≤ 10¹⁵

---

입출력 예

numbers	result
[2,7]	[3,11]

---

입출력 예 설명

입출력 예 #1

• 문제 예시와 같습니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

 

# 출제 의도 : 비트 연산을 적절히 응용할 수 있는지
# f(x)는 다음과 같이 재해석될 수 있다. 
# => ......0 x + 1 - 0
# => .....01 x + 2 - 1
# => ....011 x + 4 - 2
# => ...0111 x + 8 - 4
# => ..01111 x + 16 - 8

# 먼저 x에 어떤 수를 더하는 행위는, 다르게 해석하면 x의 특정 비트 몇 개를 골라 반전시키는 행위로 해석할 수 있다.
# ex) 10 + 3은 10의 첫 3개의 비트를 반전시키는 것으로 해석할 수 있다.
# 여기서 우리는 x의 비트를 딱 하나 또는 두 개만 바꾸어야 합니다. 그러면서 동시에 x의 값을 이전보다 더 크게 키워야 함.
# 만약 x의 비트를 하나만 바꿀 경우, x는 커져야 하기 때문에 x의 어떤 0을 1로 바꿔야 하는데, 그렇다면 x가 가진 0 중에서 가장 낮은 위치에
# 있는 0을 1로 바꾸는 것이 이상적. x가 짝수인 경우가 바로 이 경우.

# 만약 x의 비트를 2개 바꿀 경우, 일단 하나의 0은 1로 바꿔야 하는데, 다른 하나는 그보다 좀 더 낮으면서 제일 높은 자리의 1을 0으로 바꾸는 것이 더 이상적.
# 왜냐하면, 비트는 윗자리로 갈수록 그 비트가 의미하는 값이 항상 커지기 때문에. x가 홀수인 경우가 바로 이 경우

# def solution(numbers):
#     return [num + ((num ^ (num + 1)) >> 2) + 1 for num in numbers]

# def solution(numbers):
#     answer = []
#     for n in numbers :
#         num = n
#         cnt = 0
#         while n % 2 == 1 :
#             cnt += 1
#             n //= 2
#         answer.append(num + 2**(cnt-1) if cnt != 0 else num+1)
#     return answer

def solution(numbers) :
    answer = []
    for num in numbers :
        if num % 2 == 0 :
            answer.append(num + 1)
        else :
            zero_bit = ((num ^ (num + 1)) >> 2) + 1
            answer.append(num + zero_bit)
    return answer

오늘의 키워드 : 비트 연산

문제에서는 주어진 숫자의 이진 표현에서 가장 오른쪽 비트에서부터 최초로 0이 등장하는 위치를 찾고, 그 위치를 1로 바꾸어 최소값을 구하라고 합니다. 이 과정은 실제로 주어진 숫자에 가장 오른쪽에서 처음으로 등장하는 0 이전의 마지막 1 빝츠에 해당하는 수를 더함으로써 달성할 수 있습니다.

 

비트 연산 이해 :

1. XOR 연산(^) : 두 비트가 서로 다르면 1, 같으면 0을 반환
2. 오른쪽 시프트 연산 (>>) : 비트를 오른쪽으로 이동시키며, 왼쪽에는 0이 채워짐.

문제 해결 방식 :

1. 최초로 0이 등장하는 위치 찾기 : num ^ (num + 1)연산은 num과 num + 1의 이진 표현에서 서로 다른 비트를 1로 만듭니다. 주어진 num이 홀수일 경우, 가장 오른쪽 비트는 항상 1이고, num + 1에서는 해당 위치가 0으로 바뀝니다. 따라서, 이 연산 후 가장 오른쪽 비트부터 연속된 1의 시퀀스는 num의 가장 오른쪽 비트 위치를 나타냅니다.
2. 오른쪽 시프트 연산으로 조정 : (num ^ (num + 1)) >> 2 연산은 이 연속된 1들을 오른쪽으로 두 칸 이동시킵니다. 이는 마지막 1 비트 이전의 0 비트 위치에 해당하는 값을 구하기 위한 것입니다.
3. 1을 더해 최종 값 조정 : 마지막으로 1을 더해주면, 가장 오른쪽에서 처음으로 0이 나오는 위치에 1을 추가하는 것과 같은 효과를 낼 수 있습니다.

예시:

num = 13 (이진수: 1101)인 경우를 살펴봅시다.

1. num ^ (num + 1) = 1101 ^ 1110 = 0011
2. (0011 >> 2) = 0000
3. 0000 + 1 = 0001

이는 우리가 13(1101)에 1을 더해 최종 값을 14(1110)로 만들어야 함을 의미합니다. 

따라서, 이 문제의 해결책은 주어진 숫자의 이진 표현에서 가장 오른쪽의 0을 찾아 1로 바꾸는 것이며, 이를 효율적으로 수행하기 위해 비트 연산을 사용합니다.