문제 개요
이 문제에서는 하나의 이진 문자열(binary string)이 주어지며, 문자열에서 요소를 정확히 하나 제거했을 때 전체 비트의 XOR 값이 0이 되도록 만들 수 있는 경우의 수를 구해야 합니다.
예제를 통해 문제를 더 구체적으로 살펴보겠습니다.
입력
n = 11010
출력
3
"11010"에는 1이 3개(홀수) 있으므로, 1 중 하나를 제거하면 XOR이 0이 됩니다. 제거할 수 있는 1은 총 3개이므로 정답은 3입니다.
핵심 아이디어
XOR 연산의 기본 성질을 활용하면 문제를 간단하게 해결할 수 있습니다. 여러 비트를 XOR할 때 1의 개수가 짝수면 결과는 0, 홀수면 결과는 1이 됩니다. 이 성질을 바탕으로 다음과 같은 규칙을 도출할 수 있습니다.
- 1의 개수가 짝수인 경우: 문자열 전체의 XOR은 이미 0입니다. 이때 0을 제거해도 XOR 값은 변하지 않으므로, 0의 개수만큼 방법이 존재합니다.
- 1의 개수가 홀수인 경우: 1을 하나 제거해야 XOR이 0이 됩니다. 반대로 0을 제거하는 것은 XOR에 아무런 영향을 주지 않습니다. 따라서 1의 개수만큼 방법이 존재합니다.
결국 문자열을 한 번만 순회하면서 1과 0의 개수를 세기만 하면 O(n) 시간 복잡도로 답을 구할 수 있습니다.
C++ 구현
위 접근 방식을 구현한 프로그램은 다음과 같습니다.
예제 코드
#include<iostream>
#include<string.h>
using namespace std;
int wayXorZero(string binaryString){
int oneCount = 0, zeroCount = 0;
int n = binaryString.length();
for (int i = 0; i < n; i++)
if (binaryString[i] == '1')
oneCount++;
else
zeroCount++;
if (oneCount % 2 == 0)
return zeroCount;
return oneCount;
}
int main(){
string binaryString = "10110100";
cout<<"Number of ways to make XOR zero is "<<wayXorZero(binaryString);
return 0;
}
실행 결과
Number of ways to make XOR zero is 4
예제 문자열 "10110100"에는 1이 4개(짝수), 0이 4개 포함되어 있습니다. XOR이 이미 0이므로 0을 제거하는 4가지 방법이 모두 유효하며, 프로그램 역시 4를 출력합니다.
복잡도 분석
- 시간 복잡도: O(n) — 문자열을 한 번만 순회합니다.
- 공간 복잡도: O(1) — 카운터 변수 두 개만 사용합니다.