파이썬)광물캐기 -프로그래머스

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

프로그래머스

 

from collections import deque

def solution(picks, minerals):
    answer = 0
    pickable_minerals = minerals[: sum(picks) * 5]
    tools_len = 0
    for i in picks:
        tools_len += i * 5
    # print(tools_len,len(minerals))
    # print(tools_len < len(minerals))
    new_arr = []
    
    if tools_len <= len(minerals):
        for i in range(tools_len):
            new_arr.append(minerals[i])
    else:
         new_arr =  minerals
    
    minerals = []
    
    for i in range(0,len(new_arr),5):
        minerals.append(new_arr[i:i+5])
    
    minerals.sort( key=lambda x: (-x.count('diamond'), -x.count('iron')))
    q = deque(minerals)
    
    new_tools = deque(picks)
    
    while new_tools and q:
        tool = new_tools.popleft()
        
        while tool > 0 and q:
            tool -= 1
            mine = q.popleft()
            
            for i in mine:
                if i == 'diamond':
                    if len(new_tools) == 2 :
                        answer += 1
                    elif len(new_tools) == 1:
                        answer += 5
                    else:
                        answer += 25
                
                elif i == 'iron' :
                    if len(new_tools) == 2 or len(new_tools) == 1:
                        answer += 1
                    else:
                        answer += 5
                
                else:
                    answer += 1
                        
    return answer

나는 이 문제를 처음 브루트 포스로 시도해보았다.

브루트 포스 결과 시간오버가 발생했다.

그 다음으로는 dfs로 풀어봤는데, 그 또한 시간 오버가 나왔다.

결국 다른 이들의 풀이를 확인했다.

다른 사람들이 주로 사용한 알고리즘은 dfs와 그리디 였는데, 나는 이번엔 그리디로 풀어봤다.

우선 곡괭이는 한 번 집으면 5번을 "무조건" 사용해야 하는데 곡괭이 개수는 광물 *5와 같다. 즉 곡괭이 개수 * 5 가 광물의 개수와 같은지 비교해야 한다.

비교 후 더 많은 광물은 뒤에서 부터 자른 후 광물을 5개씩 묶어 다이아가 많은 광물순으로 sort해준다.

그 이후는 다이아 곡괭이부터 차례대로 앞에 광물부터 캐내면 된다.