0과 1만 포함하는 길이 N의 배열이 제공됩니다. 값 1은 서쪽 방향으로 가는 자동차를 나타내고 값 0은 동쪽 방향으로 가는 자동차를 나타냅니다.
자동차 A와 자동차 B의 쌍이 0<=A
예를 들어 이해하자
입력 - arr[] ={1,0,1,0,1}
출력 − 통과하는 자동차 쌍의 수는 다음과 같습니다. 3
설명 - 인덱스 0이 1보다 작은 (0,1) 쌍은 - (arr[1],arr[2]), (arr[1],arr[4]), (arr[3],arr [4])
입력 - arr[] ={1,0,0,0,0}
출력 − 지나가는 자동차 쌍의 수:0
설명 - 0의 인덱스가 1보다 작은 (0,1) 쌍이 없습니다.
우리는 두 가지 접근 방식을 사용할 것입니다. 두 개의 for 루프를 사용하는 최초의 순진한 접근 방식. 배열 순회를 시작합니다. 0이 발견되면 해당 지점에서 끝까지 배열을 다시 탐색하고 1을 만나면 카운트를 증가시킵니다.
0과 1을 포함하는 배열 arr[]를 사용합니다.
count_cars(int arr[], int size) 함수는 배열과 길이를 입력으로 받아 지나가는 차량의 수를 반환합니다.
초기 카운트를 0으로 합니다.
인덱스 i=0에서 i
arr[i]가 0이면 인덱스 j=i+1에서 j
각 arr[j]에 대해 1 증분으로 쌍(arr[i],arr[j])은 (0,1)이고 i
마침내 우리는 총계를 얻게 될 것입니다.
결과로 카운트를 반환합니다.
이 접근 방식에서는 끝에서 배열을 탐색합니다. 끝에서 모두 1을 센다. 각 처음 0(끝부터)에 대해 아니요. 쌍의 수는 임시인 1로 계산됩니다.
0과 1을 포함하는 배열 arr[]를 사용합니다.
count_cars(int arr[], int size) 함수는 배열과 길이를 입력으로 받아 지나가는 차량의 수를 반환합니다.
초기 카운트를 0으로 합니다.
크기>=1까지 while 루프를 사용하여 끝에서 배열을 탐색합니다.
arr[size-1]이 1이면 지금까지 찾은 1만큼 변수 temp를 증가시킵니다.
그렇지 않으면 0입니다(remp인 모든 1보다 낮은 인덱스를 가짐). 쌍은 임시 것입니다. 카운트 =카운트+온도 설정.
다음 요소의 크기를 줄입니다.
마침내 우리는 총계를 얻게 될 것입니다.
결과로 카운트를 반환합니다.
위의 코드를 실행하면 다음 출력이 생성됩니다 -
위의 코드를 실행하면 다음 출력이 생성됩니다 -아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
효율적인 접근
예(순진한 접근 방식)
#include<bits/stdc++.h>
using namespace std;
int count_cars(int arr[], int size){
int count = 0;
for (int i=0; i<size-1; i++){
if(arr[i] == 0){
for (int j=i+1; j<size; j++)
if (arr[j]==1){
count++;
}
}
}
return count;
}
int main(){
int arr[] = {1, 1, 0, 0, 1};
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"Count of passing car pairs are: "<<count_cars(arr, size);
return 0;
} 출력
Count of passing car pairs are: 2
예시(효율적인 접근)
#include<bits/stdc++.h>
using namespace std;
int count_cars(int arr[], int size){
int count = 0;
int temp = 0;
while (size >= 1){
if (arr[size-1] == 1){
temp++;
}
else{
count = count + temp;
}
size--;
}
return count;
}
int main(){
int arr[] = {1, 1, 0, 1, 1};
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"Count of passing car pairs are: "<<count_cars(arr, size);
return 0;
} 출력
Count of passing car pairs are: 2