LeetCode + 설명에서 피벗 인덱스 찾기 해결

질문 링크: https://leetcode.com/problems/find-pivot-index/

의문:

정수 배열nums이 주어지면 이 배열의 피벗 인덱스를 계산합니다.

설명:

먼저 예제를 살펴보고 그 이면의 논리를 이해해 봅시다.

예제에 따르면 숫자 배열이 있습니다.

인덱스와 함께 시각화하면 다음과 같은 결과를 얻습니다.



이제 이미지를 보면 왼쪽에 3개 요소, 오른쪽에 2개 요소를 추가하면 11가 됩니다. 따라서 그 사이의 요소에는 피벗 인덱스가 될 인덱스가 있습니다.
우리의 경우,Array[3] = 6 따라서 3은 피벗 인덱스입니다.

논리:

이제 피벗 인덱스를 확인하는 방법에 대한 문제를 살펴보겠습니다.

먼저 배열에 있는 모든 요소의 합을 알고 totalSum 로 표시해야 합니다. 여기서는 28입니다.

그런 다음 왼쪽 인덱스의 모든 요소의 합계를 구하고 leftSum로 표시합니다.

이제 이러한 요소로 테이블을 생성하고 우리가 가지고 있는 인덱스의 요소를 추적하고 Index[e]로 표시하고 그것이 무엇인지 확인합니다.



문제를 오른쪽에서 왼쪽으로 접근해 봅시다.

우리leftSum는 아무것도 추가하지 않았기 때문에 현재 0입니다. 그리고 Index[e]는 해당 인덱스에 있는 배열의 요소입니다.

배열의 각 항목에 대해 이 작업을 수행하면 leftSum가 leftSum에 있는 동일한 숫자와 같은 조건이 됩니다. 해당 조건 다음 인덱스는 pivot Index 입니다.

그리고 우리의 문제는 피벗 인덱스를 찾는 것입니다.

축하해요! 문제를 성공적으로 진단했습니다!

이제 우리가 얻은 결과에서 논리를 만들어 봅시다.
totalSum - leftSum - Index[e] = leftSum
이제 코드로 구현해 보겠습니다.
자바스크립트를 사용하고 있습니다.

function(index){

  // initialize the sums, 0 because we don't know the sums yet.

   let totalSum = 0; 
   let leftSum = 0; 

   // now let's calculate the total sum

   nums.forEach((element) => totalSum += element);

/* 
now we have the sum, so we want to check for the condition.
but before that, we need to loop through each element in the array.
*/

   for(let e=0; e<nums.length; e++){
      if(totalSum - leftSum - index[e] === leftSum){
         return e;
      }
      leftSum += index[e]
   }
   return -1;
}

우리는 해당 조건을 확인하고 해당 조건을 찾고 있었기 때문에 조건을 충족하면 인덱스를 반환했습니다pivot index.

정확한 조건이 통과되지 않은 경우 위 연습에서 수행한 것처럼 배열의 다른 요소를 leftSum에 추가해야 했습니다.

그리고 피벗 인덱스가 없으면 질문 요구 사항에 따라 -1을 반환합니다.

축하해요! 훌륭해!

The solution might not be optimal in terms of runtime and memory distribution, but hey, you figured out the concept behind it and implemented it!

표지 사진 작성자: Arnold Francisca on Unsplash

읽어 주셔서 감사합니다. 질문이 있으시면 언제든지 Twitter로 보내주세요.