광물캐기

 

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

프로그래머스

문제요약:

3가지 광물의 종류가 있고, 곡괭이의 종류가 있다. 곡괭이마다 각광물을 캘때 소비되는 피로도가 다르고, 5개씩 나누어 광물을 캔다고 했을 때, 피로도를 최소화 하라

 

소요시간 :

50분, 30분

난이도 2

 

1차시도 실패(시간초과):

from collections import defaultdict
from itertools import permutations

def solution(picks, minerals):
    #d,i,s
	num = []
	temp = defaultdict(int)
	for i,s in enumerate(minerals):
		if s[0] =='d':
			temp['d'] += 1
			temp['i'] += 5
			temp['s'] += 25
		if s[0] == 'i':
			temp['d'] += 1
			temp['i'] += 1
			temp['s'] += 5
		if s[0] == 's':
			temp['d'] += 1
			temp['i'] += 1
			temp['s'] += 1
		if i%5  == 4:
			num.append(temp)
			temp = defaultdict(int)
	if i%5  != 4:
		num.append(temp)
		temp = defaultdict(int)
	g = [['diamond','iron','stone'][i] for i in range(3) for _ in range(picks[i])]
	ans = []
	for new_list in list(set(permutations(g,min(len(num),sum(picks))))):
		temp = 0
		for i,k in enumerate(new_list):
			temp += num[i][k[0]]
		ans.append(temp)
	return min(ans)

모든 경우를 고려한 케이스입니다.

ex) [1, 3, 2],["diamond", "diamond", "diamond", "iron", "iron", "diamond", "iron", "stone"]

defaultdict num을 살펴보면 다음과같이 되는데, 5개씩 나누어서 다이아 곡괭이를 골랐다면 첫줄은 5의 cost가 들것이고, 아이언 곡괭이를 들었다면 17 cost가 들것이라는 문장입니다.

그후  세곡괭이종류의각각의 개수만큼 permutations함수를 통해 생성해주고, min함수를 통해, 5개씩 나눈 개수와 곡괭이의 개수중 작은것에 맞춰주었습니다. 그후 ans에 다 더한뒤 제일 작았던 케이스를 뽑는케이스 입니다.

완전탐색이기 때문에, 시간복잡도가 매우 높았고, 시간초과로 인해 통과하지 못했습니다.

 

2차시도:

def solution(picks, minerals):
    num_minerals= []
    #5개씩 나누어 그안에 각 광물의 개수 반환
    for i in range(0,len(minerals),5):
        temp = [i for i in minerals[i:min(i+5,len(minerals))]]
        num_minerals.append([temp.count('diamond'),temp.count('iron'),temp.count('stone')])
        
    #만약 광물을 5개씩 나눈행의 개수가 곡괭이의 수보다 많다면
    #뒤에 행들은 선택할 수 없으므로, 버려줍니다.
    for _ in range(len(num_minerals)-sum(picks)):
        num_minerals.pop()
        
    #선택 가능한 행들중에서 드는 코스트가 높을순으로 정렬
    num_minerals.sort(key = lambda x : (-x[0],-x[1],-x[2]))
    cost = {0:[1,1,1],1:[5,1,1],2:[25,5,1]}
    ans = 0
    
    #이제 zip함수로 합쳐주는데 이때 zip함수로 곡괭이가 많을때는 곡괭이가 탈락
    for i,new in list(zip([i for i in range(3) for _ in range(picks[i])],num_minerals)):
        #[1x3]행 리스트 두개의 내적
        ans += sum([cost[i][j]*new[j] for j in range(3)])
    return ans

사실 우선순위가 각 광물의 개수이기 때문에, 완전탐색을 할 필요가 없다고 판단, 5개씩 행으로 나누어 각광물의 개수를 만들고, 행의개수가 곡괭이보다 많다면 행의 우선순위가 높더라도 곡괭이가 모잘라 선택할 수 없기 때문에 그만큼 버려줍니다. 그후 선택가능한 행들중에서 우선순위가 높은 순으로 정렬하고, zip함수로 합쳐준뒤 내적을 진행합니다.

 

Extra :

zip함수로 두 리스트를 묶을때 개수가 더 작은 리스트를 기준으로 만들고 나머지부분은 버립니다. 이때  

from itertools import zip_longest 를 사용하면 되는데 용례를 보면

from itertools import zip_longest

a = [1, 2, 3, 4, 5]
b = ["a","b", "c"]

res = list(zip_longest(a, b))
# [(1, 'a'), (2, 'b'), (3, 'c'), (4, None), (5, None)]

res = list(zip_longest(a, b, fillvalue=0))
# [(1, 'a'), (2, 'b'), (3, 'c'), (4, 0), (5, 0)]

다음과 같이 fillvalue 파라미터를 안 설저앟면 None을 설정하면 그 값으로 나머지를 채워주는것을 확인할 수 있습니다.