C++ 배열에서 두 포인터 이동 후 왼쪽 포인터의 인덱스 구하기

이 문제에서는 크기가 N인 배열 arr[]가 주어지며, 우리의 목표는 배열에서 가능한 모든 이동을 수행한 후 왼쪽 포인터의 최종 인덱스를 찾는 것입니다.

배열을 탐색하기 위해 두 개의 포인터를 사용합니다. 하나는 왼쪽 포인터(left pointer), 다른 하나는 오른쪽 포인터(right pointer)입니다.

• 왼쪽 포인터: 인덱스 0에서 시작하며, 조건에 따라 값을 증가시켜 앞으로 이동합니다.
• 오른쪽 포인터: 인덱스 (n-1)에서 시작하며, 조건에 따라 값을 감소시켜 뒤로 이동합니다.

포인터 이동 규칙은 각 포인터가 지나온 요소들의 합을 기준으로 결정됩니다. 왼쪽 포인터의 합이 오른쪽 포인터의 합보다 작으면 왼쪽 포인터를 한 칸 증가시키고, 반대로 왼쪽 포인터의 합이 더 크면 오른쪽 포인터를 한 칸 감소시킵니다. 포인터가 이동할 때마다 해당 포인터의 합도 함께 갱신됩니다.

예제로 문제 이해하기

입력 : arr[] = {5, 6, 3, 7, 9, 4}
출력 : 2

풀이 과정 설명 −

leftPointer = 0 -> 합 = 5, rightPointer = 5 -> 합 = 4. rightPointer 이동
leftPointer = 0 -> 합 = 5, rightPointer = 4 -> 합 = 13. leftPointer 이동
leftPointer = 1 -> 합 = 11, rightPointer = 4 -> 합 = 13. leftPointer 이동
leftPointer = 2 -> 합 = 14, rightPointer = 4 -> 합 = 13. rightPointer 이동
leftPointer = 2 -> 합 = 14, rightPointer = 3 -> 합 = 20. rightPointer 이동
최종 왼쪽 포인터의 위치는 2입니다.

해결 방법

이 문제를 해결하는 간단한 방법은 두 포인터의 합을 서로 비교하면서 합이 작은 쪽의 포인터를 계속 이동시키는 것입니다. 이 과정을 반복하다가 왼쪽 포인터가 오른쪽 포인터 바로 앞(오른쪽 포인터 + 1)에 도달하면 탐색을 종료하고 왼쪽 포인터의 인덱스를 반환합니다.

구현 예제

아래 프로그램은 위에서 설명한 해결 방법의 동작을 보여줍니다.

#include <iostream>
using namespace std;
int findIndexLeftPointer(int arr[], int n) {
   if(n == 1)
      return 0;
   int leftPointer = 0,rightPointer = n-1,leftPointerSum = arr[0], rightPointerSum = arr[n-1];
   while (rightPointer > leftPointer + 1) {
      if (leftPointerSum < rightPointerSum) {
         leftPointer++;
         leftPointerSum += arr[leftPointer];
      }
      else if (leftPointerSum > rightPointerSum) {
         rightPointer--;
         rightPointerSum += arr[rightPointer];
      }
      else {
         break;
      }
   }
   return leftPointer;
}
int main() {
   int arr[] = { 5, 6, 3, 7, 9, 4 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The index of left pointer after moving is "<<findIndexLeftPointer(arr, n);
   return 0;
}

실행 결과

The index of left pointer after moving is 2