[프로그래머스 > Lv2] 광물캐기

프로그래머스

 

1. 문제

곡괭이를 하나 선택해서 광물 5개를 연속으로 캐고, 다음 곡괭이를 선택해서 광물 5개를 연속으로 캐는 과정을 반복하여, 더 사용할 곡괭이가 없거나 광산에 있는 모든 광물을 캘 때까지 과정을 반복합니다.

 

[입력]

• 곡갱이의 개수를 나타내는 정수 배열 picks
• 광물들의 순서를 나타내는 문자열 배열 materials

[결과]

작업을 끝내기까지 필요한 최소한의 피로도를 return

 

2. 풀이

🌹 완전탐색으로 풀 수 있는 문제입니다.

먼저 문제를 풀기 전에 필요한 정보를 먼저 준비하도록 하겠습니다.

 

2.1 곡갱이별 피로도

private val needs = arrayOf(
    arrayOf(1, 1, 1),
    arrayOf(5, 1, 1),
    arrayOf(25, 5, 1)
)

2.2 광물의 index

광물이 String형식으로 제공되기 때문에 이를 코드 내에서 사용하기 쉽도록 index로 바꿔주는 Map을 추가하도록 하겠습니다. 🤗

private val stones = mapOf(
	"diamond" to 0, 
    "iron" to 1,
    "stone" to 2
)

 

이제 완전탐색을 하며 피로도가 가장 낮은 경우를 찾으면 됩니다. 👍🏻

이 때, 탐색을 종료하는 조건은

1. 모든 광물을 다 캔 경우
2. 모든 곡괭이를 다 쓴 경우
3. 지금까지의 피로도가 이전에 구했던 최소 피로도보다 큰 경우 더 이상 탐색할 필요 없음

위 3가지를 코드로 나타내면 아래와 같습니다.

if (index >= minerals.size) {
    answer = min(answer, total)
    return
}
if (picks.all { it == 0 }) {
    answer = min(answer, total)
    return
}
if (answer <= total) return

 

3. 코드

Kotlin

import kotlin.math.min
class Solution {
    private val needs = arrayOf(
        arrayOf(1, 1, 1),
        arrayOf(5, 1, 1),
        arrayOf(25, 5, 1)
    )
    private val stones = mapOf("diamond" to 0, "iron" to 1, "stone" to 2)
    private var answer: Int = Int.MAX_VALUE
    fun solution(picks: IntArray, minerals: Array<String>): Int {
        solve(0, picks, minerals, 0)
        return answer
    }

    private fun solve(
        index: Int,
        picks: IntArray,
        minerals: Array<String>,
        total: Int
    ) {
        if (index >= minerals.size) {
            answer = min(answer, total)
            return
        }
        if (picks.all { it == 0 }) {
            answer = min(answer, total)
            return
        }
        if (answer <= total) return

        for (pick in 0 until 3) {
            if (picks[pick] > 0) {
                picks[pick]--
                solve(
                    index + 5, picks,
                    minerals,
                    total + calc(pick, index, minerals)
                )
                picks[pick]++
            }
        }
    }

    private fun calc(
        pick: Int,
        start: Int,
        minerals: Array<String>
    ): Int {
        var result = 0
        for (i in 0 until 5) {
            if (start + i >= minerals.size) return result
            val mineral = minerals[start + i]
            result += needs[pick][stones[mineral] ?: 0]
        }
        return result
    }
}