문제 개요
이 문제에서는 정수 N이 주어지며, 우리의 과제는 N 다음으로 오는 희소 수(sparse number)를 찾는 프로그램을 작성하는 것입니다.
희소 수(Sparse Number)란 이진수 표현에 인접한 두 개의 1이 존재하지 않는 특수한 유형의 숫자를 의미합니다.
예시: 5(101), 16(10000)
문제 설명 − 주어진 숫자 N보다 큰 수 중에서 가장 작은 희소 수를 찾아야 합니다.
예제를 통해 문제를 이해해 보겠습니다.
입력
N = 7
출력
8
설명
8의 이진수 표현은 1000이며, 인접한 1이 없으므로 N보다 큰 가장 작은 희소 수입니다.
해결 방법 1: 단순 탐색
가장 간단한 해결책은 N보다 큰 모든 숫자를 하나씩 검사하다가 처음으로 발견되는 희소 수에서 멈추는 것입니다.
이를 위해 N부터 시작하여 반복문을 돌리고, 각 숫자가 희소 수인지 확인합니다. 희소 수라면 반복을 종료하고 결과를 반환하고, 그렇지 않다면 다음 숫자로 계속 진행합니다.
솔루션의 동작을 보여주는 프로그램:
예제
#include<iostream>
using namespace std;
bool isSpareNumber(int N){
int currentBit = (N&1);
int nextBit ;
while (N!= 0){
nextBit = currentBit;
currentBit = (N&1);
N >>= 1;
if(nextBit == currentBit && nextBit == 1 && currentBit == 1)
return false ;
}
return true;
}
int findNextSparseNumber(int N) {
while(1){
if(isSpareNumber(N))
return N;
N++;
}
return -1;
}
int main() {
int N = 564;
cout<<"The number is "<<N<<endl;
cout<<"The next Sparse Number is "<<findNextSparseNumber(N);
return 0;
}출력
The number is 564 The next Sparse Number is 576
이 방법은 구현이 매우 간단하지만, N과 결과 값 사이의 거리가 클 경우 여러 번의 검사를 반복해야 하므로 시간 복잡도가 O(N·log N)까지 증가할 수 있다는 단점이 있습니다.
해결 방법 2: 비트 조작을 활용한 효율적인 접근
더 효율적인 접근 방식은 숫자의 비트를 직접 조작하는 것입니다. 숫자의 이진수 표현을 구한 뒤, 인접한 1이 나타나는 위치의 비트를 수정합니다.
최하위 비트(LSB)에서 최상위 비트(MSB) 방향으로 순회하면서 연속된 두 개의 1을 발견하면, 해당 두 비트를 모두 0으로 바꾸고 그 다음 자리 비트를 1로 설정합니다. 이 과정을 MSB에 도달할 때까지 반복한 후, 완성된 이진수를 다시 십진수로 변환하면 그것이 바로 원하는 결과입니다.
예제를 살펴보겠습니다.
N = 52
이 숫자의 이진수 표현은 110100입니다.
LSB부터 순회하며 이진수에서 첫 번째로 연속된 1의 쌍을 찾습니다. 바로 110100에서 강조된 부분입니다. 그런 다음 두 개의 1을 모두 0으로 바꾸고 다음 자리 비트에 1을 더합니다. 이렇게 하면 숫자는 1000000이 되고, 이 값을 십진수로 변환하면 64입니다.
솔루션의 동작을 보여주는 프로그램:
예제
#include<iostream>
using namespace std;
int findNextSparseNumber(int N) {
int spNum[16];
int n = 0;
while (N != 0) {
spNum[n] = (N&1);
n++;
N >>= 1;
}
n++;
int lastCorrectedBit = 0;
for (int i= 0 ; i< n; i++) {
if (spNum[i] == 1 && spNum[i-1] == 1 && spNum[i+1] != 1){
spNum[i+1] = 1;
for (int j=i; j>=lastCorrectedBit; j--)
spNum[j] = 0;
lastCorrectedBit = i+1;
}
}
int sparseNumber = 0;
for (int i =0; i<n-1; i++)
sparseNumber += spNum[i]*(1<<i);
return sparseNumber;
}
int main() {
int N = 564;
cout<<"The number is "<<N<<endl;
cout<<"The next Sparse Number is "<<findNextSparseNumber(N);
return 0;
}출력
The number is 564 The next Sparse Number is 576
마무리
비트 조작 기반 접근 방식은 숫자의 비트 길이에 비례하는 시간, 즉 O(log N)만에 결과를 얻을 수 있어 단순 탐색 방법보다 훨씬 효율적입니다. 입력 값이 커질수록 두 방법의 성능 차이는 더욱 두드러지게 나타납니다.