[leetCocd/JS] 907. Sum of Subarray Minimums

문제 설명

Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 109 + 7.

 

정수 배열에서 min(b)의 합을 구하는데, b는 arr의 모든 연속된 하위 배열이란다. 예제를 보면 이해하 간다.
숫자가 크니까 modulo로 나머지를 리턴하란다.

 

입출력 예

Example 1:

Input: arr = [3,1,2,4]
Output: 17
Explanation: 
Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.
Sum is 17.

 

Example 2:

Input: arr = [11,81,94,43,3]
Output: 444

 

Constraints

• 1 <= arr.length <= 3 * 104
• 1 <= arr[i] <= 3 * 104

 

 

 

---

 

내 솔루션

• 처음엔 이쁘게 예제와 같은 로직으로 만들었지만, 느려서 실패하고 다시 만듦.
• 무한 손코딩으로 짧게 돌방법을 찾아서 끄적거리다가 min을 정해놓고 arr[j]와 비교하면 원하는 숫자가 나와서 결정. 

var sumSubarrayMins = function(arr) {
  const MOD = 1e9 + 7;
  let sum = 0;
  for(let i = 0; i < arr.length; i++) {
    let min = arr[i];
    for(let j = i; j < arr.length; j++){
      min = Math.min(min, arr[j]);
      sum += min;
    }
  }
  return sum % MOD;
};


// 느려서 실패
var sumSubarrayMins = function(arr) {
  const MOD = 1e9 + 7;
  let sum = 0;
  for(let len = 1; len <= arr.length; len++) {
    for(let idx = 0; idx < arr.length - len + 1; idx++) {
      let temp = [];
      for(let i = 0; i < len; i++){
        temp.push(arr[idx+i])
      }
      sum += Math.min(...temp)
      temp = [];
    } 
  }
  return sum % MOD;
};

 

감상평

• 오늘의 leetCode 문제는 좀 어렵다.