하나의 이진수가 주어졌을 때, 이 수보다 크면서도 가장 작은 수, 그리고 0과 1의 개수가 원래 수와 동일한 수의 이진 표현을 찾아야 합니다. 예를 들어 입력이 1011(십진수 11)이라면 출력은 1101(십진수 13)이 됩니다. 두 수 모두 1이 세 개, 0이 한 개로 구성되어 있기 때문입니다.
이 문제는 정렬된 순열에서 바로 다음에 오는 순열을 구하는 '다음 순열(next permutation)' 계산법을 활용하면 효율적으로 해결할 수 있습니다. 아래에서 알고리즘의 동작 원리를 단계별로 살펴보겠습니다.
알고리즘
nextBin(bin) −
Begin
len := bin의 길이
i를 len-2부터 1까지 감소시키며 반복:
만약 bin[i]가 '0'이고 bin[i+1]이 '1'이면
bin[i]와 bin[i+1]의 값을 서로 교환
반복 종료(break)
end if
done
만약 i가 0이면 더 큰 수가 존재하지 않으므로 그대로 반환
그렇지 않으면 j := i + 2, k := len – 1로 설정
j < k인 동안 반복:
만약 bin[j]가 '1'이고 bin[k]가 '0'이면
bin[j]와 bin[k]의 값을 서로 교환
j는 1 증가, k는 1 감소
else if bin[j]가 '0'이면
break
else
j를 1 증가
end if
done
return bin
End
동작 원리
이 알고리즘의 핵심은 다음과 같습니다.
1단계: 교환 지점 찾기
오른쪽에서 왼쪽으로 탐색하며 '0' 뒤에 '1'이 오는 위치, 즉 "01" 패턴을 찾습니다. 이 위치를 서로 바꾸면 수가 커지면서도 변화폭이 최소화됩니다.
2단계: 나머지 비트 재배치
교환 지점 오른쪽 부분에서 '1'은 앞쪽으로, '0'은 뒤쪽으로 몰아줍니다. 이렇게 하면 전체 수를 가능한 한 작게 유지하면서 조건을 만족하는 '바로 다음' 큰 수를 얻을 수 있습니다.
예제 코드
#include <iostream>
using namespace std;
string nextBinary(string bin) {
int len = bin.size();
int i;
// 오른쪽에서부터 "01" 패턴 탐색
for (i = len - 2; i >= 1; i--) {
if (bin[i] == '0' && bin[i+1] == '1') {
char ch = bin[i];
bin[i] = bin[i+1];
bin[i+1] = ch;
break;
}
}
// 더 큰 수가 없는 경우
if (i < 1)
return "No greater number is present";
int j = i + 2, k = len - 1;
// 남은 구간에서 1은 앞으로, 0은 뒤로 정렬
while (j < k) {
if (bin[j] == '1' && bin[k] == '0') {
char ch = bin[j];
bin[j] = bin[k];
bin[k] = ch;
j++;
k--;
}
else if (bin[j] == '0')
break;
else
j++;
}
return bin;
}
int main() {
string bin = "1011";
cout << "Binary value of next greater number = " << nextBinary(bin);
}
출력 결과
Binary value of next greater number = 1101
정리
입력 1011의 경우, 먼저 오른쪽에서 "01" 패턴을 찾아 1011 → 1101로 첫 번째 비트를 교환합니다. 이후 나머지 구간을 확인하여 이미 조건을 만족하므로 최종 결과인 1101(십진수 13)이 출력됩니다. 이 알고리즘은 문자열 길이에 대해 선형 시간 O(n)으로 동작하므로 매우 효율적입니다.