이 문제에서는 정수 X가 주어지며, 우리의 목표는 0에서 X로 변환하는 데 필요한 총 단계 수 중 최댓값을 구하는 것입니다.
유효한 변환의 정의
유효한 변환이란 A에서 B로 한 번 변환이 일어날 때 하나의 단계로 계산되는 것을 말합니다. 변환이 성립하려면 다음 두 조건을 만족해야 합니다.
- A != B (두 값이 서로 달라야 함)
- A & B = A (여기서 &는 비트 AND 연산자)
즉, 한 단계는 A에서 B로의 변환이며, 우리는 0에서 X로 변환하는 최대 단계 수를 계산하는 프로그램을 작성해야 합니다.
문제 이해를 위한 예시
입력 - X = 7
출력 - 3
설명 - 0에서 7로 변환하는 과정은 다음과 같습니다.
Step1: 0(00) → 1(01), 0 != 1이고 0&1 = 0이므로 00 => 01 변환
Step2: 1(001) → 3(011), 1 != 3이고 1&3 = 1이므로 001 => 011 변환
Step3: 3(0011) → 7(0111), 3 != 7이고 3&7 = 3이므로 0011 => 0111 변환
접근 방법
이 문제를 해결하는 핵심 아이디어는 X에 포함된 설정된 비트(set bit), 즉 값이 1인 비트의 개수를 세는 것입니다. 그 개수가 곧 0에서 X로 변환하는 최대 단계 수가 됩니다.
최대 변환을 얻으려면 각 설정된 비트마다 한 단계씩 순차적으로 진행해야 합니다. 비트를 하나씩 차례로 켜 나가는 방식이 0에서 X로 변환하는 최대 단계 수를 보장합니다.
A에서 B로의 변환에서는 A의 모든 설정된 비트가 B에도 포함되어 있어야 하지만, 그 반대는 필수가 아닙니다. 따라서 최소 변환 횟수는 1이 될 수 있습니다. 0에는 설정된 비트가 전혀 없기 때문에 가장 작은 변환이 직접적으로 가능하기 때문입니다.
위 예시에서 확인할 수 있듯이, 각 숫자의 이진수 표현과 비트 AND 연산 결과를 통해 변환 조건이 어떻게 충족되는지 살펴볼 수 있습니다.
구현 예제
다음은 위 솔루션을 C++로 구현한 프로그램입니다.
#include <bits/stdc++.h>
using namespace std;
int maxtransformation(int x){
int steps = 0;
// 설정된 비트 개수 세기
while (x) {
steps += x & 1;
x >>= 1;
}
return steps;
}
int main(){
int x = 7;
cout<<"The maximum number of steps to transform 0 to "<<x<<" with bitwise AND are "<<maxtransformation(x);
return 0;
}
출력 결과
The maximum number of steps to transform 0 to 7 with bitwise AND are 3
복잡도 분석
시간 복잡도: O(log X) - X의 비트 수만큼 반복문이 실행됩니다.
공간 복잡도: O(1) - 추가적인 메모리 공간을 사용하지 않습니다.