문제 개요
이 문제에서는 크기가 n인 이진 문자열 배열 bin[]이 주어지며, 배열에 포함된 모든 문자열에 대해 비트 OR(Bitwise OR) 연산을 수행한 결과를 구하는 것이 목표입니다.
즉, 다음과 같이 모든 문자열의 비트 OR를 계산해야 합니다.
bin[0] | bin[1] | ... | bin[n-2] | bin[n-1]
예시
입력:
bin[] = {"1001", "11001", "010101"}출력:
011101
설명: 모든 이진 문자열의 비트 OR 결과는 다음과 같습니다.
(1001) | (11001) | (010101) = 011101
해결 접근 방법
이 문제는 다음 단계로 해결할 수 있습니다.
먼저 비트 길이가 가장 긴 문자열(최대 길이 문자열)을 찾습니다. 그다음, 나머지 모든 문자열 앞에 필요한 만큼의 선행 0(leading zero)을 추가하여 길이를 맞춰줍니다. 마지막으로 길이가 동일해진 문자열들을 대상으로 각 자리별로 비트 OR 연산을 수행하면 됩니다.
알고리즘 동작 과정
예시를 통해 알고리즘이 어떻게 동작하는지 살펴보겠습니다.
bin[] = {"1101", "011010", "00111"}최대 길이 문자열은 길이가 6인 "011010"입니다. 따라서 나머지 문자열들 앞에 0을 채워 길이를 맞춥니다.
업데이트된 문자열: "001101", "011010", "000111"
모든 문자열의 비트 OR를 계산하면 다음과 같습니다.
001101 | 011010 | 000111 = 011111
C++ 구현 코드
위에서 설명한 해결 방법을 구현한 프로그램은 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
string bitwiseOR(string* bin, int n){
string result;
int max_size = INT_MIN;
// 최대 길이를 구하고 각 문자열을 뒤집어 오른쪽 정렬 준비
for (int i = 0; i < n; i++) {
max_size = max(max_size, (int)bin[i].size());
reverse(bin[i].begin(), bin[i].end());
}
// 부족한 길이만큼 뒤에 0을 붙임 (원본 기준 선행 0)
for (int i = 0; i < n; i++) {
string s;
for (int j = 0; j < max_size - bin[i].size(); j++)
s += '0';
bin[i] = bin[i] + s;
}
// 각 자리별로 모든 문자열의 비트 OR 계산
for (int i = 0; i < max_size; i++) {
int insertBit = 0;
for (int j = 0; j < n; j++)
insertBit = insertBit | (bin[j][i] - '0');
result += (insertBit + '0');
}
// 결과를 원래 순서로 되돌림
reverse(result.begin(), result.end());
return result;
}
int main() {
string bin[] = { "1101", "011010", "00111" };
int n = sizeof(bin) / sizeof(bin[0]);
cout << "배열 내 모든 이진 문자열의 비트 OR 결과: " << bitwiseOR(bin, n);
return 0;
}실행 결과
배열 내 모든 이진 문자열의 비트 OR 결과: 011111
코드 동작 원리
이 구현의 핵심은 각 문자열을 먼저 뒤집는(reverse) 부분입니다. 문자열을 뒤집으면 서로 다른 길이의 이진수를 오른쪽 끝자리를 기준으로 정렬할 수 있으며, 뒤집힌 상태에서 문자열 뒤에 0을 붙이는 것은 원본 문자열 앞에 선행 0을 붙이는 것과 같은 효과를 냅니다.
이후 세 번째 반복문에서 각 인덱스 위치마다 모든 문자열의 해당 비트를 OR 연산하여 결과를 만들고, 마지막에 다시 뒤집어 원래 순서의 결과를 반환합니다.
마무리
이 방식의 시간 복잡도는 O(n × L)입니다. 여기서 n은 문자열의 개수, L은 최대 문자열 길이입니다. 문자열을 직접 다루므로 이진 문자열이 매우 길어져 정수형 범위를 초과하더라도 안전하게 비트 OR 연산을 처리할 수 있다는 장점이 있습니다.