광물 캐기

문제

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

접근 방식

그리디 방식으로 접근했다.

문제의 조건들을 모아보면:

- 곡괭이별 광물 캐기 피로도는 정해져 있다 (다이아 > 철 > 돌 순서)
- 한번 주워 든 곡괭이는 5개의 광물을 캐고 더 이상 쓸 수 없음. 사용 순서는 정해지지 않음.
- 광물은 주어진 순서대로만 캘 수 있음
- 모든 광물을 캐거나, 더 사용할 곡괭이가 없을 때까지 광물 캐기

가장 피로도가 많이 드는 광물 목록은 우선적으로 다이아 > 철 > 돌 곡괭이로 처리하는 게 최선의 방식이라는 점은 확실하다.

그러므로 피로도가 많이 드는 광물 묶음 순서로 정렬한 뒤, 이를 적은 피로도로 캘 수 있는 곡괭이를 활용하여 처리하면 된다. 이를 위해 광물 목록을 5개씩 짤라서 정렬한 뒤, 곡괭이로 차례대로 처리했을 때의 비용을 계산했다.

다만, 광물을 묶을 때 곡괭이를 다 쓰고 광물이 남은 경우를 고려해야 한다(=TC8)
왜냐하면 뒤에 위치한 광물을 우선적으로 캐지 못하는데, 모든 광물을 5개 묶음으로 짤라서 정렬하면 그런 경우가 발생할 수 있기 때문이다.
👉 광물은 주어진 순서대로만 캘 수 있음 조건 고려

코드

from collections import deque


def calc(cur_p, cur_m):
    if cur_p == 'diamond':
        return cur_m[0] * 1 + cur_m[1] * 1 + cur_m[2] * 1
    if cur_p == 'iron':
        return cur_m[0] * 5 + cur_m[1] * 1 + cur_m[2] * 1
    if cur_p == 'stone':
        return cur_m[0] * 25 + cur_m[1] * 5 + cur_m[2] * 1


def counter(arr):
    count = [0] * 3  # [d, i, s] 순으로 개수
    for x in arr:
        if x == 'diamond':
            count[0] += 1
        elif x == 'iron':
            count[1] += 1
        else:
            count[2] += 1
    return count


def solution(picks, minerals):
    # minerals 5개 묶음으로 전처리 (비용 큰 순 정렬)
    mineral_data = []
    cnt, i = 0, 0  # 곡괭이 개수만큼 짜르기 !! (minerals 전체 짜르기 -> TC8 반례)
    while cnt < sum(picks) and i < len(minerals):
        mineral_data.append(counter(minerals[i:i+5]))
        i += 5
        cnt += 1
    mineral_data.sort(reverse=True)
    mq = deque(mineral_data)

    # picks -> 개수만큼 배열로
    pq = deque(picks[0] * ['diamond'] + picks[1] * ['iron'] + picks[2] * ['stone'])

    # Greedy 수행
    fatigue = 0
    while pq and mq:
        px = pq.popleft()
        mx = mq.popleft()

        fatigue += calc(px, mx)

    return fatigue