[Python] 프로그래머스 : 광물 캐기 (그리디 알고리즘)

출처 : 프로그래머스 코딩테스트 연습,https://school.programmers.co.kr/learn/courses/30/lessons/172927

def solution(picks, minerals):
    answer = 0
    
    dia_mapping = {"diamond":1,"iron":1,"stone":1}
    iron_mapping = {"diamond":5,"iron":1,"stone":1}
    stone_mapping = {"diamond":25,"iron":5,"stone":1}
    
    dia_picker = picks[0]
    iron_picker = picks[1]
    stone_picker = picks[2]
    
    #미네랄을 5단위로 끊어서 새로운 리스트를 만든다.
    #슬라이스 연산자로 곡괭이의 개수만큼 잘라준다.
    minerals = [minerals[i:i+5] for i in range(0,len(minerals),5)][:sum(picks)]
    
    #그리디 알고리즘을 위해 minerals_5 의 정렬이 필요하다.
    # 다이아몬드, 철, 돌의 개수에 따라 내림차순으로 정렬
    #print(minerals)
    minerals.sort(key = lambda x : (x.count("diamond"),x.count("iron"),x.count("stone")), reverse = True)
    #print(minerals)
    
    for mineral in minerals:
        
        if dia_picker > 0 :
            for name in mineral:
                answer += dia_mapping[name]
            dia_picker -= 1
            
        elif iron_picker > 0:
            for name in mineral:
                answer += iron_mapping[name]
            iron_picker -= 1
        
        elif stone_picker > 0:
            for name in mineral:
                answer += stone_mapping[name]
            stone_picker -= 1

    return answer

 

그리디 알고리즘의 핵심은, 내가 이득을 취하고자 하는 순서대로 데이터를 정렬을 하는것이다.

 

문제를 읽다보면 , 곡괭이에 대해서만 정렬을 사용해야 할 것 같지만,

 

실상은 반대로 광물에 대해서 정렬을 취하게 되면 문제를 해결 가능하다.

 

문제의 조건에 맞게 광물을 5개씩만 잘라서 새로운 리스트를 만든 뒤에

 

그 새로운 리스트를 곡괭이의 총 개수에 근거하여 다시 실제로 연산에 사용할 부분만 남겨둔다.

 

이 과정에서 슬라이스 연산자와 , key를 이용한 정렬이 필요하다.

 

즉 minerals 를 정렬할때에 내부의 원소들(광물이름이 5개씩 잘라져서 들어있는 리스트)에서 가장 이득인 광물의 숫자가 많은 순서대로 정렬을 해야한다.

 

그 이후에 dictionary를 통해 매핑을 한 피로도 점수를 answer에 더해주면 된다.