[프로그래머스 LV.2] 광물 캐기

문제

문제 풀이

처음에는 위상정렬로 풀어야 하나 하다가 레벨 2인데 설마 하면서 그리디로 한번 풀어봤습니다. 나중에 보니 BFS로 푸는 분들도 있더라구요. 근데 그게 그거인듯? 풀이 순서는 아래와 같습니다.

1. 광물을 캘 수 있는 만큼만 자르기(곡괭이의 수에 맞춰서)
2. 5개씩 묶어서 돌 곡괭이(최악의 경우)를 기준으로 가중치 먹여서 리스트로 정리하기
3. 가중치가 높은 순으로 정렬( reverse=True로 해둬야 가중치가 높은 순으로 정렬)
4. 해당 리스트를 좋은 곡괭이부터 사용해서 채굴
5. 채굴하는 공괭이와 광물의 종류에 따라 분기하며 answer에 피로도를 더해주면 끝

풀이 코드

def solution(picks, minerals):
    answer = 0
    
    # 캘 수 있는 광물의 최대 개수만큼만 자르기
    total_picks = sum(picks)
    minerals = minerals[:total_picks * 5]
    
    # 광물을 5개씩 묶어서 피로도 가중치 계산
    grouped_minerals = []
    for i in range(0, len(minerals), 5):
        chunk = minerals[i:i+5]
        
        # 돌 곡괭이(최악의 경우)로 캤을 때의 피로도를 기준으로 가중치 산정
        weight = 0
        for m in chunk:
            if m == 'diamond': weight += 25
            elif m == 'iron': weight += 5
            else: weight += 1
            
        # (가중치, 광물 묶음) 저장
        grouped_minerals.append([weight, chunk])
    
    # 가중치가 높은(캐기 힘든) 순서대로 정렬. 힙큐를 해서 저장해도 되는데 코드도 길어지고 sort도 nlogn인걸로 알아서 그냥 정렬
    grouped_minerals.sort(reverse=True)
    
    # 정렬된 광물 묶음을 순서대로 좋은 곡괭이부터 사용하여 채굴 => 이거 때문에 그리디인듯?
    for _, chunk in grouped_minerals:
        if picks[0] > 0: # 다이아
            picks[0] -= 1
            answer += len(chunk)
        elif picks[1] > 0: # 철
            picks[1] -= 1
            for m in chunk:
                if m == 'diamond': answer += 5
                else: answer += 1
        elif picks[2] > 0: # 돌
            picks[2] -= 1
            for m in chunk:
                if m == 'diamond': answer += 25
                elif m == 'iron': answer += 5
                else: answer += 1
        else:
            break # 곡괭이 앵꼬
            
    return answer