[Programmers] 광물 캐기

 

코드

# 복습 횟수:0, 01:00:00, 복습필요:***
from collections import deque
def solution(picks, minerals):
    answer = 0
    mineral_list = []
    tool_num = sum(picks)
    minerals = minerals[:5*tool_num]

    tmp = []
    for idx, mineral in enumerate(minerals):
        tmp.append(mineral)
        if idx % 5 == 4:
            mineral_list.append(tmp)
            tmp = []
        else:
            pass
    
    if len(tmp) != 0:
        mineral_list.append(tmp)
    
    indexed_list = []
    for mineral in mineral_list:
        dia = 0
        iron = 0
        stone = 0
        for m in mineral:
            if m == "diamond":
                dia += 1
            elif m == "iron":
                iron += 1
            else:
                stone += 1
        indexed_list.append([dia, iron, stone])

    indexed_list.sort(key=lambda x:[-x[0], -x[1], -x[2]])

    tool_list = deque()
    for idx, pick in enumerate(picks):
        if idx == 0:
            for i in range(pick):
                tool_list.append("dia")
        elif idx == 1:
            for i in range(pick):
                tool_list.append("iron")
        else:
            for i in range(pick):
                tool_list.append("stone")

    
    for dia_num, iron_num, stone_num in indexed_list:

        tool = tool_list.popleft()
        if tool == "dia":
            answer  = answer + (dia_num + iron_num + stone_num)
        elif tool == "iron":
            answer = answer + (dia_num * 5 + iron_num + stone_num)
        else:
            answer = answer + (dia_num * 25 + iron_num * 5 + stone_num)

    return answer

print(solution([0, 0, 1], ["diamond", "diamond", "diamond", "diamond", "diamond", "iron", "iron", "iron", "iron", "iron", "diamond"]))

 

 

구현 + greedy 느낌의 문제

greedy임은 각 5개마다의 곡괭이에서 diamond의 수, iron의 수, stone의 수에 따라서 이미 그 부분에서 순서가 다 결정되기 때문입니다. 

이  문제에서 가장 중요한 것은 minerals = minerals[:5*tool_num] 인데

예를 들어 곡괭이가 2개이고, 광물 집합이 3개인 경우에는 광물 집합 1, 2만을 캘 수 있습니다. 하지만 제 위의 코드처럼 sort하는 경우 캐지 못하는 3번째 광물 집합이 캐지는 모순이 발생할 수 있습니다. 따라서 위와같이 집합을 잘라주어 문제를 해결하였습니다.