문제 수를 세는 C++ 프로그램은 목록의 왼쪽 또는 오른쪽 끝에서 해결할 수 있습니다.

n개의 요소가 있는 배열 A가 있고 다른 숫자 k가 있다고 가정합니다. 한 대회에 n개의 문제가 있다고 가정합니다. Amal의 문제 해결 능력은 k입니다. Amal은 항상 목록의 끝에서 문제를 해결합니다. 그리고 그는 난이도가 k보다 큰 문제를 풀 수 없습니다. 그는 왼쪽과 오른쪽 문제의 난이도가 k보다 클 때 멈춥니다. 우리는 그가 풀 수 있는 문제의 수를 계산해야 합니다. A[i]는 i번째 문제의 난이도를 나타냅니다.

따라서 입력이 A =[4, 2, 3, 1, 5, 1, 6, 4]와 같으면; k =4이면 출력은 5가 됩니다. 처음에는 4로 가장 왼쪽의 문제를 풀고, 4로 가장 오른쪽에 있는 문제를 풀고, 그 다음에는 가장 오른쪽에 있는 문제를 더 이상 풀 수 없고, 그 다음 왼쪽부터 난이도 2, 3, 1로 문제를 풀기 때문입니다. 총 5개의 문제를 풀 수 있습니다.

단계

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n := size of A
l := 0
r := n - 1
for initialize i := 0, when i < n, update (increase i by 1), do:
   if A[i] <= k and l is same as i, then:
      (increase l by 1)
while A[r] <= k, do:
   (decrease r by 1)
if l is same as n, then:
   return n
Otherwise
   return n - 1 - r + l

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A, int k) {
   int n = A.size();
   int l = 0, r = n - 1;
   for (int i = 0; i < n; ++i) {
      if (A[i] <= k && l == i)
         ++l;
   }
   while (A[r] <= k)
      --r;
   if (l == n)
      return n;
   else
      return n - 1 - r + l;
}
int main() {
   vector<int> A = { 4, 2, 3, 1, 5, 1, 6, 4 };
   int k = 4;
   cout << solve(A, k) << endl;
}

입력

{ 4, 2, 3, 1, 5, 1, 6, 4 }, 4

출력

5