문제 소개
이진수가 하나 주어졌을 때, 비트를 정확히 하나 제거하여 남은 수가 가능한 모든 경우 중 가장 큰 값이 되도록 만드는 문제입니다. 예시를 통해 살펴보겠습니다.
입력 : N = 1011 출력 : 111 설명 : 비트 하나를 제거해야 합니다. 0을 제거하면 111이 되지만, 1을 제거하면 101 또는 011이 됩니다. 111 > 101, 011이므로 0을 제거하는 것이 가장 큰 값을 만듭니다. 입력 : 111 출력 : 11 설명 : 모든 비트가 1이므로 어떤 비트를 제거하더라도 결과는 동일합니다.
접근 방법
브루트 포스(완전 탐색) 방식
가장 단순한 방법은 각 비트를 하나씩 차례대로 제거해 본 뒤, 그 결과값들을 서로 비교하여 최댓값을 찾는 것입니다. 이 방법 역시 정확한 답을 보장하지만, 모든 경우를 일일이 시도해야 하므로 비효율적입니다.
반면 훨씬 효율적인 접근 방식이 존재합니다. 바로 결과 숫자에 가장 적은 영향을 미치는, 즉 가장 덜 필요한 비트를 제거하는 것입니다.
효율적인 접근 방식
효율적인 방법은 결과 숫자에 미치는 영향을 최소화합니다.
왼쪽(최상위 비트)부터 오른쪽으로 비트를 순회합니다.
처음 등장하는 0을 찾아 즉시 제거합니다.
0이 하나도 없다면(모든 비트가 1이라면) 어떤 비트를 제거해도 결과가 같으므로 아무 비트나 제거합니다.
왼쪽에서부터 첫 번째 0을 제거하는 것이 최선인 이유는, 그 자리에 더 높은 자릿수의 1이 당겨져 오기 때문에 다른 어느 비트를 제거하는 경우보다 항상 같거나 더 큰 값을 얻게 되기 때문입니다.
C++ 구현 예제
효율적인 접근 방식의 C++ 코드
#include <bits/stdc++.h>
using namespace std;
int main(){
string str = "1011";
bool flag = false;
int n = str.length();
// 결과를 저장할 새 배열 선언
char res[n - 1];
int j = 0;
// 왼쪽부터 이진수를 순회
for (int i = 0; j < n - 1; i++) {
// 0을 발견하면 건너뜀 (한 번만)
if (str[i] == '0' && flag == false) {
flag = true;
continue;
}
else
res[j++] = str[i];
}
// 결과 문자열 출력
cout << "Maximum number: " << res;
return 0;
}실행 결과
Maximum number: 111
코드 설명
flag 변수를 사용하여 0을 딱 한 번만 제거하도록 처리했습니다.
결과 숫자를 저장하기 위해 문자 배열 res를 선언했습니다.
원래 숫자보다 하나 적은 요소를 저장해야 하므로 반복문은 n-1개의 문자까지만 채웁니다.
마무리
이 글에서는 이진수에서 비트 하나를 제거했을 때 만들 수 있는 최댓값을 구하는 문제를 다뤘으며, 브루트 포스 방식과 첫 번째 0을 제거하는 효율적인 방식, 두 가지 접근 방법을 살펴보았습니다. 소개한 C++ 코드는 C, Java, Python 등 다른 언어로도 손쉽게 작성할 수 있습니다. 이 튜토리얼이 여러분에게 도움이 되기를 바랍니다.