貪婪的小偷

這是來自 LIOJ 上的題目，因為陷阱還蠻特別的，所以想記錄下來。

魔鬼藏在細節裡

我想很多人應該都很困惑明明在自己電腦跑都 OK，但系統還是一直噴 Wrong Answer (´⊙ω⊙`)

我其實也搞了老半天才發現，但在討論陷阱之前，先談談這題的解法。

這題的解法其實不難，就是「根據小偷可以偷的數量，把每樣物品價格由大到小做加總」，所以我是這樣做的：

1. 把物品陣列做排序，由大排到小
2. 把陣列加總，從第一個加到第 n 個（n = 小偷能偷的總數量）

function solve(lines) {
  // 小偷能偷到的總金額
  let totalValue = 0
  // 小偷能帶走物品的最大數量
  const max = Number(lines[0])
  // 所有物品（除掉前兩筆元素）
  const items = transformToNumber(lines.slice(2))

  // 重新排序，由大排到小
  items.sort((a, b) => b - a)
  // 把陣列加總
  for(let i=0; i<max; i++) {
    totalValue += items[i]
  }
  console.log(totalValue)
}
// 轉換成 Number 型態
function transformToNumber(arr) {
  let result = []
  for(let i=0; i<arr.length; i++) {
    result.push(Number(arr[i]))
  }
  return result 
}
solve(['3', '5', '1', '3', '5', '7', '9']) // 21

這樣子看起來沒有什麼問題，範例給的測試資料也能得到正確結果。

凡事都要設想周到

但是！有一件很重要的事情被忽略了：如果小偷能偷的數量 >= 所有物品的數量呢？

沒有錯，我想這一題 AC 率會那麼低就是因為很多人跟我一樣都忽略掉了這件事，所以才會懷疑人生老半天。

先讓我們看看如果在「能偷的數量 >= 物品的數量」的情況會發生什麼：

solve(['100', '5', '1', '3', '5', '7', '9'])

答案是 NaN，問題出在這一段：

// 把陣列加總
for(let i=0; i<max; i++) {
    totalValue += items[i]
}

陣列的物品只有 [1, 3, 5, 7, 9] 這五個，而 max 是 100，也就是說這個迴圈會從 0 跑到 99。

所以請想想看，在 item[5] 的時候會發生什麼？

// 迴圈跑到第六圈（i = 5）
totalValue +=  undefined 

現在你知道為什麼會冒出 NaN 了吧。

正確的作法

經過剛剛的教訓後，我們可以修正成這樣：

function solve(lines) {
  // 小偷能偷到的總金額
  let totalValue = 0
  // 小偷能帶走物品的最大數量
  const max = Number(lines[0])
  // 物品的總數量
  const totalItem = Number(lines[1])
  // 所有物品（除掉前兩筆元素）
  const items = transformToNumber(lines.slice(2))

  /*
    Edge case：
    小偷可以偷的數量 >= 所有物品的數量
    這時後的答案就變成是陣列總和
  */
  if(max >= totalItem) {
    for(let i=0; i<items.length; i++) {
      totalValue += items[i]
    }
    console.log(totalValue)
  } else {
    // 重新排序，由大排到小
    items.sort((a, b) => b - a)
    // 切割出可偷的物品陣列
    for(let i=0; i<max; i++) {
      totalValue += items[i]
    }
    console.log(totalValue)
  }
}
// 轉換成 Number 型態
function transformToNumber(arr) {
  let result = []
  for(let i=0; i<arr.length; i++) {
    result.push(Number(arr[i]))
  }
  return result 
}
solve(['100', '5', '1', '3', '5', '7', '9']) // 25

利用 slice() 寫出更簡潔的作法

除了用 for 迴圈來求陣列總和以外，你也可以換個思維：

1. 把物品陣列做排序，由大排到小
2. 切割出物品陣列的範圍，從 0 切到 n 的範圍（n = 小偷能偷的總數量）
3. 把切割出的陣列加總

所以最後會寫出這樣子的程式碼：

function solve(lines) {
  // 小偷能偷到的總金額
  let totalValue = 0
  // 小偷能帶走物品的最大數量
  const max = Number(lines[0])
  // 物品的數量 
  const totalItem = Number(lines[1])
  // 所有物品（除掉前兩筆元素）
  const items = transformToNumber(lines.slice(2))
  
  // 重新排序，由大排到小
  items.sort((a, b) => b - a)
  // 切割出可偷的物品陣列
  const availableItems = items.slice(0, max)
  // 計算陣列總和
  totalValue = availableItems.reduce((acc, elem) => acc + elem, 0)
  console.log(totalValue)
}
// 轉換成 Number 型態
function transformToNumber(arr) {
  let result = []
  for(let i=0; i<arr.length; i++) {
    result.push(Number(arr[i]))
  }
  return result 
}

之所以可以省略掉判斷的原因是因為這一句：

const availableItems = items.slice(0, max)

如果把 slice() 的第二個參數設成比陣列長度大的數字，會自動視為是最後一個元素的意思。因此 max 不管是多大的數字，availableItems 都會是一個完整的陣列。