개념
배열 N, 다른 키 X 및 세그먼트 크기 K를 갖는 주어진 배열 arr1[]과 관련하여 작업은 arr1[]에서 키 X가 크기 K의 모든 세그먼트에 존재하는지 확인하는 것입니다.
입력
arr1[] = { 4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4}
X = 4
K = 3 출력
Yes
배열 {4, 6, 3}, {5, 10, 4}, {2, 8, 4} 및 {12, 13, 4}에는 크기가 K인 겹치지 않는 4개의 세그먼트가 있습니다. 4는 모든 세그먼트에 있습니다.
입력
arr1[] = { 22, 24, 57, 66, 35, 55, 77, 33, 24, 46, 22, 24, 26}
X = 24
K = 5 출력
Yes
입력
arr1[] = { 6, 9, 8, 13, 15, 4, 10}
X = 9
K = 2 출력
No
방법
이 경우 개념은 간단합니다. 크기 K의 모든 세그먼트를 고려하고 X가 창에 있는지 여부를 확인합니다. 따라서 마지막 세그먼트를 신중하게 처리해야 합니다.
예시
다음은 위의 접근 방식을 구현한 것입니다 -
// C++ code to determine the every segment size of
// array have a search key x
#include <bits/stdc++.h>
using namespace std;
bool findxinkindowSize1(int arr1[], int X, int K, int N){
int i;
for (i = 0; i < N; i = i + K) {
// Search X in segment starting
// from index i.
int j;
for (j = 0; j < K; j++)
if (arr1[i + j] == X)
break;
// If loop didn't break
if (j == K)
return false;
}
// If N is a multiple of K
if (i == N)
return true;
// Check in last segment if N
// is not multiple of K.
int j;
for (j=i-K; j<N; j++)
if (arr1[j] == X)
break;
if (j == N)
return false;
return true;
}
// main driver
int main(){
int arr1[] = { 4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4 };
int X = 4, K = 3;
int N = sizeof(arr1) / sizeof(arr1[0]);
if (findxinkindowSize1(arr1, X, K, N))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
} 출력
Yes