M번의 범위 토글 연산 후 이진 배열 결과 구하기

이번 글에서는 이진 배열과 범위 토글(range toggle) 연산을 다루는 문제를 살펴보겠습니다. 길이가 n인 이진 배열이 있으며, 각 원소는 0 또는 1입니다. 처음에는 배열의 모든 원소가 0으로 초기화되어 있습니다.

여기에 총 M개의 명령이 주어집니다. 각 명령은 시작 인덱스와 끝 인덱스를 포함하며, command(a, b)는 배열의 a번째 위치부터 b번째 위치까지의 모든 원소에 적용됩니다. 명령의 역할은 해당 범위 내 값들을 토글(toggle)하는 것입니다. 즉, 0은 1로, 1은 0으로 뒤집습니다.

문제 자체는 단순하지만, 알고리즘의 동작 과정을 정확히 이해하는 것이 중요합니다. 아래에서 순서대로 확인해 보겠습니다.

알고리즘

toggleCommand(arr, a, b)

Begin
   a부터 b까지의 각 원소 e에 대해,
      e의 값을 토글하여 arr의 해당 위치에 저장한다.
   반복 종료
End

이 방식은 각 명령마다 최대 n개의 원소를 순회하므로, 전체 시간 복잡도는 O(M × N)입니다. M과 n이 크지 않다면 충분히 효율적이지만, 입력이 매우 큰 경우 차분 배열(difference array)과 누적 합을 활용하면 O(N + M)으로 개선할 수 있습니다.

예제 코드

#include <iostream>
using namespace std;

void toggleCommand(int arr[], int a, int b){
   for(int i = a; i <= b; i++){
      arr[i] ^= 1; // a부터 b까지의 각 비트를 토글
   }
}

void display(int arr[], int n){
   for(int i = 0; i < n; i++){
      cout << arr[i] << " ";
   }
   cout << endl;
}

int main() {
   int arr[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
   int n = sizeof(arr)/sizeof(arr[0]);
   display(arr, n);
   toggleCommand(arr, 3, 6);
   toggleCommand(arr, 8, 10);
   toggleCommand(arr, 2, 7);
   display(arr, n);
}

실행 결과

0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 1 1 1 0

실행 결과를 살펴보면, 초기 상태에서는 모든 원소가 0입니다. 이후 세 번의 토글 명령이 순서대로 적용됩니다.

• (3, 6): 인덱스 3~6이 1로 변경
• (8, 10): 인덱스 8~10이 1로 변경
• (2, 7): 인덱스 2~7이 다시 토글되어, 기존에 1이었던 3~6은 0으로 돌아가고 2와 7은 1로 변경

최종적으로 인덱스 2, 7, 8, 9, 10만 1이 되고 나머지는 0으로 출력됩니다. XOR 연산(^= 1)을 사용하면 조건문 없이 간결하게 비트를 반전시킬 수 있다는 점이 이 풀이의 핵심입니다.