C++에서 배열을 아름답게 만드는 데 필요한 최소 작업 찾기

이 문제에서는 0과 1이 되는 n개의 이진 값으로 구성된 이진 배열 bin[]이 주어집니다. 우리의 임무는 배열을 아름답게 만드는 데 필요한 최소 연산을 찾는 것입니다.

아름다운 배열은 0과 1이 번갈아 나타나는 패턴으로 구성된 특수한 유형의 이진 배열입니다.

문제 설명 − 배열을 아름답게 만드는 데 필요한 숫자 연산을 찾아야 합니다. 작업은 다음 단계로 구성됩니다. -

1단계 − 어레이를 두 부분으로 자릅니다.

2단계 − 두 반쪽 중 하나를 뒤집습니다.

3단계 − 합류했다가 반감합니다.

어레이가 아름다운 어레이가 되도록 하는 데 필요한 작업의 수를 계산할 것입니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력

bin[] = {1, 0, 1, 0, 0, 1}

출력

1

설명

배열을 자르고 하위 배열 bin[4, 5]을 만들고 반전시킨 다음 다시 결합합니다.

솔루션 접근 방식

문제에 대한 솔루션은 연속적인 0의 수와 동일한 스위치 작업의 최소 수를 찾는 것을 기반으로 합니다. 기본 사례는 -

배열의 크기가 1이면 아름다운 배열입니다. 배열의 크기가 홀수이면 결코 아름다운 배열이 될 수 없습니다.

모든 짝수 길이에 대해 수행할 작업의 수가 될 연속 0 또는 1의 총 수를 확인합니다.

알고리즘

초기화 - zeroCount, oneCount, consZero =0

1단계 - if ( n =1)이면 0을 반환

2단계 - (n%2 !=0)인 경우 -1을 반환합니다.

3단계 − i -> 0에서 n-1까지 루프

3.1단계 - bin[i] ==bin[i+1] ==0이면 consZero++입니다.

4단계 - bin[n-1] ==bin[0] ==0인 경우 consZero++.

5단계 - consZero를 반환합니다.

우리 솔루션의 작동을 설명하는 프로그램

예시

#include <iostream>
using namespace std;
int minOperations(int bin[], int n) {
   if(n == 1)
      return 0;
   if(n%2 != 0)
      return -1;
      int consZero = 0;
   for (int i = 0; i < n; ++i) {
      if (i + 1 < n) {
         if (bin[i] == 0 && bin[i + 1] == 0)
            consZero++;
      }
   }
   if (bin[0] == bin[n - 1] && bin[0] == 0)
      consZero++;
      return consZero;
}
int main() {
   int bin[] = { 1, 0, 1, 0, 0, 1};
   int n = sizeof(bin) / sizeof(bin[0]);
   cout<<"The minimum operations needed to make an Array beautiful is "<<minOperations(bin, n);
   return 0;
}

출력

The minimum operations needed to make an Array beautiful is 1