문제 개요
이 문제에서는 크기가 n인 이진 문자열 배열 bin[]이 주어지며, N개의 이진 문자열 전체에 대한 비트 AND(&) 연산 결과를 구하는 프로그램을 작성해야 합니다. 즉, 배열의 모든 요소를 다음과 같이 AND 연산하는 것입니다.
bin[0] & bin[1] & ... & bin[n-2] & bin[n]
예시로 문제 이해하기
입력:
bin[] = {"1001", "11001", "010101"}출력:
000001
설명: 세 이진 문자열의 비트 AND 연산 결과는 다음과 같습니다.
(1001) & (11001) & (010101) = 000001
방법 1: 순차적 AND 연산 (기본 접근법)
가장 직관적인 해결 방법은 두 이진 문자열의 비트 AND를 먼저 구한 뒤, 그 결과를 다음 문자열과 계속 AND 연산하여 배열의 마지막 요소까지 반복하는 것입니다.
기본 알고리즘 단계:
초기값 → result = bin[0], i = 1
1단계 − 배열이 끝날 때까지 2단계와 3단계를 반복합니다.
2단계 − result = result & bin[i]
3단계 − i 값을 1 증가시킵니다.
4단계 − 최종 결과를 출력합니다.
실행 과정 살펴보기
위 접근법으로 예제를 직접 풀어보겠습니다.
bin[] = {"1001", "11001", "010101"}
result = bin[0] = 1001, i = 1반복 1:
result = 1001 & 11001 = 01001 i = 2
반복 2:
result = 01001 & 010101 = 000001 i = 3. 종료
구현 코드
위 해결 방법을 보여주는 프로그램입니다.
#include <iostream>
using namespace std;
int changeLength(string &a, string &b){
int lengtha = a.length();
int lengthb = b.length();
int zeros = abs(lengtha-lengthb);
if (lengtha<lengthb) {
for (int i = 0 ; i<zeros; i++)
a = '0' + a;
return lengthb;
}
else {
for (int i = 0 ; i<zeros; i++)
b = '0' + b;
}
return lengtha;
}
string bitwiseAND(string binary1, string binary2){
int length = changeLength(binary1,binary2);
string result = "";
for (int i = 0 ; i<length; i++){
result = result+(char)((binary1[i] - '0' & binary2[i]-'0')+'0');
}
return result;
}
int main(){
string bin[] = {"1001", "11001", "010101"};
int n = sizeof(bin)/sizeof(bin[0]);
string result;
if (n<2){
cout<<bin[n-1]<<endl;
}
else{
result = bin[0];
for (int i = 1; i<n; i++)
result = bitwiseAND(result, bin[i]);
cout <<result<<endl;
}
}출력:
000001
이 방법은 구현이 간단하지만, 문자열 길이를 맞추기 위해 매번 문자열을 순회해야 하므로 효율성 면에서는 아쉬움이 있습니다.
방법 2: 최소 길이 기준 최적화 접근법
이제 더 효율적인 해결 방법을 살펴보겠습니다. 핵심 아이디어는 다음과 같습니다.
먼저 이진수들 중 가장 짧은 길이와 가장 긴 길이를 찾습니다. 그다음 가장 짧은 길이 범위 내에서 각 자릿수별로 비트 AND를 계산하고, 마지막에 앞부분에 0을 채워 넣습니다. 여기서 0의 개수는 최대 길이에서 최소 길이를 뺀 값입니다. 이는 길이가 짧은 수의 앞자리가 사실상 0으로 채워져 있다고 볼 수 있기 때문입니다.
동작 원리 예시
샘플 예제를 통해 솔루션을 명확히 이해해 보겠습니다.
bin[] = {"1001", "11001", "010101"}
최대 길이 = 010101, 최소 길이 = 1001
010101 & 1001 = 00001구현 코드
위 접근법의 구현을 보여주는 프로그램입니다.
#include <bits/stdc++.h>
using namespace std;
string bitwiseANDarray(string* bin, int n){
string result;
int minSize = INT_MAX;
int maxSize = INT_MIN;
for (int i = 0; i < n; i++) {
reverse(bin[i].begin(), bin[i].end());
minSize = min(minSize, (int)bin[i].size());
maxSize = max(maxSize, (int)bin[i].size());
}
for (int i = 0; i < minSize; i++) {
bool setBit = true;
for (int j = 0; j < n; j++) {
if (bin[j][i] == '0') {
setBit = false;
break;
}
}
result += (setBit ? '1' : '0');
}
for (int i = 0; i<abs(maxSize-minSize); i++)
result += '0';
reverse(result.begin(), result.end());
return result;
}
int main(){
string arr[] = {"1001", "11001", "010101"};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<bitwiseANDarray(arr, n);
return 0;
}출력:
000001
마무리
C++에서 N개의 이진 문자열의 비트 AND를 구하는 두 가지 방법을 살펴보았습니다. 첫 번째 방법은 이해하기 쉽지만 문자열을 반복적으로 순회해야 하는 반면, 두 번째 방법은 최소 길이만큼만 연산하여 불필요한 작업을 줄일 수 있습니다. 실제 프로젝트에서는 데이터 크기와 요구 사항에 따라 적절한 방법을 선택하시기 바랍니다.