C++를 사용하여 배열에서 마지막으로 제거된 요소의 위치 찾기

이 문제에서는 크기가 N이고 정수 값 M인 배열 arr[]이 제공됩니다. 우리의 임무는 배열에서 마지막으로 제거된 요소의 위치를 ​​찾는 것입니다. .

배열에서 값을 제거하는 작업은 −

• arr[i]배열의 요소. arr[i]> M이면 값을 팝하고 arr[i] - M을 배열의 끝으로 누릅니다. 그렇지 않으면 어레이에서 제거하십시오.

배열이 요소로 구성될 때까지 작업을 수행합니다.

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

입력

arr[] = {5, 4, 8}, M = 3

출력

3

설명

Removing values using operations,
{5, 4, 8} -> {4, 8, 2} -> {8, 1, 2} -> {1, 2, 5} -> {2, 5} -> {5} -> {2} ->
empty array.
The last value removed is 8, position is 3.

솔루션 접근 방식

문제에 대한 간단한 해결책은 마지막으로 제거될 각 값이 ceil(arr[i] / M)의 가장 큰 값을 갖는다는 사실을 사용하여 제거할 마지막 값을 찾는 것입니다. .

배열을 마지막으로 종료하는 요소의 위치를 ​​찾기 위해 배열을 순회하고 최대값이 ceil(arr[i] / M)인 위치를 저장합니다. .

예시

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

#include <iostream>
using namespace std;
int findLastRemPos(int arr[], int n, int m){
   for (int i = 0; i < n; i++) {
      arr[i] = (arr[i] / m + (arr[i] % m != 0));
   }
   int lastRemPos = -1, largestVal = -1;
   for (int i = n - 1; i >= 0; i--) {
      if (largestVal < arr[i]) {
         largestVal = arr[i];
         lastRemPos = i;
      }
   }
   return lastRemPos + 1;
}
int main(){
   int arr[] = {5, 4, 8, 1};
   int n = sizeof(arr) / sizeof(arr[0]);
   int m = 3;
   cout<<"The position of last removed element in the array is "<<findLastRemPos(arr, n, m);
   return 0;
}

출력

The position of last removed element in the array is 3