C++에서 이진 배열의 하위 배열의 10진수 값에 대한 쿼리

문제 설명 − 여기에서 각 쿼리를 해결하려면 L에서 R로 시작하는 하위 배열, 즉 하위 배열[L...R]에 의해 생성된 10진수를 찾아 인쇄해야 합니다.

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

입력

bin[] = {1, 1, 0, 0, 1, 0, 1, 0, 0, 0}
Q = 2
2 5
0 6

출력

2 101

설명

쿼리 1의 경우 구성되는 하위 배열은 { 0, 0, 1, 0}입니다. 십진수 변환이 2인 이진수 0010을 생성합니다.

쿼리 2의 경우 구성되는 하위 배열은 { 1, 1, 0, 0, 1, 0, 1}입니다. 10진수 변환이 101인 이진수 1100101을 생성합니다.

솔루션 접근 방식

간단한 솔루션 인덱스 L에서 인덱스 R로 이진 문자열을 탐색하고, 형성된 이진수를 찾은 다음, 주어진 이진수를 해당하는 십진수로 변환합니다.

우리의 접근 방식의 구현을 보여주는 프로그램

예시

#include <iostream>
#include <math.h>
using namespace std;

int CalcDecimalValue(int bin[], int L, int R) {
   int decimal = 0;
   int j = 0;
   for(int i = R; i >= L; i--){
      decimal += bin[i] * pow(2, j);
      j++;
   }
   return decimal;
}

int main() {
   
   int bin[] = {1, 1, 0, 0, 1, 0, 1, 0, 0, 0};
   int n = sizeof(bin) / sizeof(bin[0]);
   int Q = 2;
   int query[Q][2] = {{2, 5},{0, 6}};
   for(int i = 0; i < Q; i++){
      cout<<"For query "<<(i+1)<<": The decimal value of subarray is "<<CalcDecimalValue(bin, query[i]   [0], query[i][1])<<"\n";
   }
   return 0;
}

출력

For query 1: The decimal value of subarray is 2
For query 2: The decimal value of subarray is 101

또 다른 접근 방식 문제를 해결하는 방법은 미리 계산된 배열을 사용하는 것입니다. (n-i)번째 인덱스 값까지 생성된 십진수를 저장할 미리 계산된 배열을 생성합니다. 그리고 쿼리를 풀기 위해 l과 r의 값 사이의 차이를 찾을 것입니다.

배열의 i번째 값은 2진수에서 10진수로의 변환 공식을 사용하여 찾을 수 있습니다. 오른쪽에서 적용, 즉 n-1에서

decimalArray[i] =bin[i]*2^(n-1-i) + bin[i+1]*2^(n-1-i+1) + … bin[n-1]*2^( 0).

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

예시

#include <bits/stdc++.h>
using namespace std;
int decimalArray[1000];

void createDecimalArray(int bin[], int n){
   memset(decimalArray, 0, n*sizeof(int));
   decimalArray[n - 1] = bin[n - 1] * pow(2, 0);
   for (int i = n - 2; i >= 0; i--)
   decimalArray[i] = decimalArray[i + 1] + bin[i] * (pow(2,(n - 1 - i)));
}

int CalcDecimalValue(int L, int R, int n){
   if (R != n - 1)
   return (decimalArray[L] - decimalArray[R + 1]) / (pow(2, (n - 1 - R)));
   return decimalArray[L] / (1 << (n - 1 - R));
}

int main(){

   int bin[] = {1, 1, 0, 0, 1, 0, 1, 0, 0, 0};
   int n = sizeof(bin) / sizeof(bin[0]);
   createDecimalArray(bin, n);
   int Q = 2;
   int query[Q][2] = {{2, 5},{0, 6}};
   for(int i = 0; i < Q; i++){
      cout<<"For query "<<(i+1)<<": The decimal value of subarray is "<<CalcDecimalValue(query[i][0],    query[i][1], n)<<"\n";
   }
   return 0;
}

출력

For query 1: The decimal value of subarray is 2
For query 2: The decimal value of subarray is 101