BOJ 12813 - 이진수 연산

문제

길이가 같은 두 이진수 문자열에 대해 AND, OR, XOR, NOT A, NOT B 연산 결과를 각각 출력하라.

입력

길이 100,000인 두 이진수 문자열이 주어진다.

출력

5줄에 걸쳐 AND, OR, XOR, NOT A, NOT B 결과를 출력한다.

예제

입력	출력
`110` `101`	`100` `111` `011` `001` `010`

풀이

두 이진수를 정수 배열로 변환 후 각 자리에 비트 연산을 적용한다.

문자열을 정수 배열로 변환한다
각 자리에 대해 &, |, ^ 연산을 수행하여 출력한다
NOT 연산은 ! 연산자로 비트를 반전하여 출력한다

핵심 아이디어: 문자열의 각 자리를 독립적으로 비트 연산하면 O(L)에 해결된다.

코드

#include <iostream>
#include <cstring>
#include <stdlib.h>
 
using namespace std;
 
int main()
{
  int A[100001], B[100001];
  string strA, strB;
  cin >> strA >> strB;
  int i = strA.length() - 1;
  while (i != -1)
  {
    A[i] = strA[i] - '0';
    B[i] = strB[i] - '0';
    i--;
  }
 
  int len = strA.length();
  for (i = 0; i < len; i++)
    printf("%d", A[i] & B[i]);
  printf("\n");
 
  for (i = 0; i < len; i++)
    printf("%d", A[i] | B[i]);
  printf("\n");
 
  for (i = 0; i < len; i++)
    printf("%d", A[i] ^ B[i]);
  printf("\n");
 
  for (i = 0; i < len; i++)
    printf("%d", !A[i]);
  printf("\n");
 
  for (i = 0; i < len; i++)
    printf("%d", !B[i]);
  printf("\n");
}

복잡도

시간: O(L) (L: 이진수 문자열 길이)
공간: O(L)

문제