[Algorithm] 광물 캐기

[hwangJi-dev]

💬 문제

https://school.programmers.co.kr/learn/courses/30/lessons/172927

💬 Idea

<그리디>

• 곡괭이를 하나 선택해서 광물 5개를 연속으로 캐기 위해서 for문을 5씩 기준으로 돈다.

  • 이 때, 캐야 할 광물이 5개 미만으로 남은 경우 해당 개수만큼 캐준다.
  • 연속으로 캔 광물을 하나씩 돌면서, diamond, iron, stone에 각각 차등적으로 점수(25, 5, 1)를 더하여 우선순위를 만들어 sumArrByStoneTools 배열에 저장한다.

• 이후 곡괭이가 먼저 소진되는 경우 해당 곡괭이 수에 비례하는 광물 개수만 캐기 위해 해당 작업을 처리해주고,
  우선순위가 높은 순서대로 sumArrByStoneTools 배열을 정렬한다. →

  if sumArrByStoneTools.count > maxToolCount {
   sumArrByStoneTools = Array(sumArrByStoneTools[0..<maxToolCount])
  }
  
  sumArrByStoneTools = sumArrByStoneTools.sorted(by: { $0.1 > $1.1 })

• 그 다음 picks가 모두 0이 되어 곡괭이가 소진되는 경우, sumArrByStoneTools를 모두 다 돈 경우가 아닐 때까지 반복하며 정답을 구한다.

  • 다이아몬드 곡괭이가 남아있다면, 다이아몬드 곡괭이를 우선적으로 소진한다. (다이아 → 철 → 돌 순)

  if picks[0] > 0 {
   picks[0] -= 1
   sum += calSum(1, sumArrByStoneTools[idx].0)
   } else if picks[1] > 0 {
   picks[1] -= 1
   sum += calSum(2, sumArrByStoneTools[idx].0)
   } else {
   picks[2] -= 1
   sum += calSum(3, sumArrByStoneTools[idx].0)
   }
   

  <합계 구하는 메서드>

  func calSum(_ type: Int, _ minerals: [String]) -> Int {
   let toolDict: [Int : [Int]] = [1: [1, 1, 1], 2: [5, 1, 1], 3: [25, 5, 1]]
   var sum = 0
   
   for i in minerals {
   if i == "diamond" {
   sum += toolDict[type]![0]
   } else if i == "iron" {
   sum += toolDict[type]![1]
   } else {
   sum += toolDict[type]![2]
   }
   }
   
   return sum
  }

💬 풀이

import Foundation

func solution(_ picks:[Int], _ minerals:[String]) -> Int {
 var sumArrByStoneTools: [([String], Int)] = []
 let maxToolCount = picks.reduce(0, +)
 
 for i in stride(from: 0, to: minerals.count, by: 5) {
 var gijoon = 0
 
 if i + 4 < minerals.count {
 gijoon = i + 4
 } else {
 gijoon = minerals.count - 1
 }
 
 let m = minerals[i...gijoon].map({ String($0) })
 var temp = 0
 
 for j in m {
 if j == "diamond" {
 temp += 25
 } else if j == "iron" {
 temp += 5
 } else {
 temp += 1
 }
 }
 
 sumArrByStoneTools.append((m, temp))
 }
 
 if sumArrByStoneTools.count > maxToolCount {
 sumArrByStoneTools = Array(sumArrByStoneTools[0..<maxToolCount])
 }
 
 sumArrByStoneTools = sumArrByStoneTools.sorted(by: { $0.1 > $1.1 })
 
 var sum = 0
 var idx = 0
 var picks = picks
 
 while picks.allSatisfy({ $0 == 0 }) == false && idx < sumArrByStoneTools.count {
 if picks[0] > 0 {
 picks[0] -= 1
 sum += calSum(1, sumArrByStoneTools[idx].0)
 } else if picks[1] > 0 {
 picks[1] -= 1
 sum += calSum(2, sumArrByStoneTools[idx].0)
 } else {
 picks[2] -= 1
 sum += calSum(3, sumArrByStoneTools[idx].0)
 }
 
 idx += 1
 }
 
 return sum
}

func calSum(_ type: Int, _ minerals: [String]) -> Int {
 let toolDict: [Int : [Int]] = [1: [1, 1, 1], 2: [5, 1, 1], 3: [25, 5, 1]]
 var sum = 0
 
 for i in minerals {
 if i == "diamond" {
 sum += toolDict[type]![0]
 } else if i == "iron" {
 sum += toolDict[type]![1]
 } else {
 sum += toolDict[type]![2]
 }
 }
 
 return sum
}