728x90
📌 링크: https://school.programmers.co.kr/learn/courses/30/lessons/172927
📌 틀린이유:
✅ 최적의 순서를 알 수 없다고 생각해서 완전 탐색인 permutation을 썼는데 시간초과가 났다.
=> 광물들을 5개씩 묶고 피로도가 높은 순서로 정렬한 다음 다이아몬드,철,돌 순서로 곡괭이를 소모하면 되는 문제였다.
✅ 광물 배열을 곡괭이로 캘수 있는 정도까지만 잘라줘야한다. => 안해줘서 피로도 순서가 꼬였고 그래서 최적이 안되게 되버렸다.
📌 알고리즘
1️⃣ 광물을 전체 곡괭이 개수*5만큼으로 잘라준다.(캘 수 있는 만큼)
def solution(picks, minerals):
s_p = sum(picks)
num = s_p * 5
if len(minerals)>s_p:
minerals = minerals[:num]
2️⃣ 광물들을 5개씩 묶고 한 배열에 [다이아몬드 개수, 철 개수, 돌 개수] 를 계산해서 넣어준다.
dic = {"diamond":0,"iron":1,"stone":2}
m_list = [[0,0,0] for _ in range(len(minerals)//5+1)]
for i in range(len(minerals)):
idx = dic[minerals[i]]
m_list[i//5][idx]+=1
3️⃣ 광물들을 피로도 순서로 정렬한다. 이때 많은순 정렬이므로 -x[n]으로 작성했다.(다이아몬드 많은 순 > 철 개수 많은 순 > 돌 개수 많은 순)으로 정렬
m_list.sort(key=lambda x: (-x[0],-x[1],-x[2]))
4️⃣ 다이아몬드 곡괭이부터 소진하게 한다.
answer = 0
for d,i,s in m_list:
if picks[0]==0 and picks[1]==0 and picks[2]==0:
break
elif picks[0]>0:
answer+=(d+i+s)
picks[0]-=1
continue
elif picks[1]>0:
answer+=(d*5+i+s)
picks[1]-=1
continue
elif picks[2]>0:
answer+=(d*25+i*5+s)
picks[2]-=1
continue
5️⃣ 정답을 낸다.
return answer
📌 전체 코드:
def solution(picks, minerals):
s_p = sum(picks)
num = s_p * 5
if len(minerals)>s_p:
minerals = minerals[:num]
dic = {"diamond":0,"iron":1,"stone":2}
m_list = [[0,0,0] for _ in range(len(minerals)//5+1)]
for i in range(len(minerals)):
idx = dic[minerals[i]]
m_list[i//5][idx]+=1
m_list.sort(key=lambda x: (-x[0],-x[1],-x[2]))
answer = 0
for d,i,s in m_list:
if picks[0]==0 and picks[1]==0 and picks[2]==0:
break
elif picks[0]>0:
answer+=(d+i+s)
picks[0]-=1
continue
elif picks[1]>0:
answer+=(d*5+i+s)
picks[1]-=1
continue
elif picks[2]>0:
answer+=(d*25+i*5+s)
picks[2]-=1
continue
return answer
728x90