문제 요약
다이아몬드, 철, 돌 곡괭이는 한 번 선택하면 최대 5개의 광물을 연속해서 캔다. 광물은 주어진 순서를 바꿀 수 없으며, 가진 곡괭이를 모두 사용하거나 모든 광물을 캐면 작업을 끝낸다.
목표는 곡괭이를 사용하는 순서를 적절히 정해 총 피로도를 최소화하는 것이다.
핵심 아이디어
곡괭이 하나는 정확히 최대 5개 광물을 캐므로, 광물 목록을 5개 단위 묶음으로 나눌 수 있다.
곡괭이 수가 부족하면 실제로 캘 수 있는 광물까지만 고려한다. 이후 묶음은 어떤 방법으로도 캘 수 없으므로 답에 영향을 주지 않는다.
각 묶음에서 다이아몬드, 철, 돌의 개수를 센다. 다이아몬드 곡괭이와 돌 곡괭이의 피로도 차이는 다음과 같다.
| 광물 | 다이아 곡괭이 | 돌 곡괭이 | 차이 |
|---|---|---|---|
| diamond | 1 | 25 | 24 |
| iron | 1 | 5 | 4 |
| stone | 1 | 1 | 0 |
따라서 다이아몬드와 철이 많은 묶음일수록 좋은 곡괭이를 사용했을 때 절약되는 피로도가 크다.
그래서 광물 묶음을 diamond 개수 -> iron 개수 -> stone 개수 내림차순으로 정렬하고, 다이아몬드 곡괭이부터 차례대로 배정한다.
풀이 과정
- 사용할 수 있는 곡괭이 개수의 합을 구한다.
min(len(minerals), 곡괭이 수 * 5)까지만 광물을 고려한다.- 광물을 5개씩 묶고 각 묶음의 광물 개수를 센다.
- 묶음을 다이아몬드, 철, 돌 개수 기준 내림차순 정렬한다.
- 좋은 곡괭이부터 묶음 하나씩 배정해 피로도를 더한다.
Python 코드
def solution(picks, minerals):
# 곡괭이로 실제로 캘 수 있는 광물까지만 고려한다.
max_minerals = min(len(minerals), sum(picks) * 5)
groups = []
# 광물을 5개 단위로 나누고, 각 묶음의 구성 정보를 저장한다.
for start in range(0, max_minerals, 5):
group = minerals[start:start + 5]
diamond_count = group.count("diamond")
iron_count = group.count("iron")
stone_count = group.count("stone")
groups.append((diamond_count, iron_count, stone_count))
# 좋은 곡괭이가 필요한 묶음부터 처리한다.
groups.sort(reverse=True)
fatigue = 0
pick_index = 0 # 0: 다이아몬드, 1: 철, 2: 돌
for diamond_count, iron_count, stone_count in groups:
# 현재 종류의 곡괭이가 없으면 다음 종류로 넘어간다.
while pick_index < 3 and picks[pick_index] == 0:
pick_index += 1
if pick_index == 3:
break
if pick_index == 0: # 다이아몬드 곡괭이
fatigue += diamond_count + iron_count + stone_count
elif pick_index == 1: # 철 곡괭이
fatigue += diamond_count * 5 + iron_count + stone_count
else: # 돌 곡괭이
fatigue += diamond_count * 25 + iron_count * 5 + stone_count
picks[pick_index] -= 1
return fatigue정당성 설명
두 묶음 A, B가 있고, A가 B보다 다이아몬드 수가 많거나 같으며 다이아몬드 수가 같다면 철 수가 많거나 같다고 하자.
좋은 곡괭이를 B에, 나쁜 곡괭이를 A에 배정한 경우를 생각할 수 있다. 좋은 곡괭이를 A에, 나쁜 곡괭이를 B에 배정하도록 서로 바꾸면 다이아몬드와 철에서 발생하는 피로도 차이가 더 큰 A가 더 큰 이득을 얻는다. 돌은 어떤 곡괭이로 캐도 피로도가 같거나, 좋은 곡괭이를 배정해도 불리해지지 않는다.
따라서 좋은 곡괭이를 다이아몬드와 철이 많은 묶음에 배정하는 것이 항상 최적이다. 모든 묶음을 이 기준으로 내림차순 정렬한 뒤 다이아몬드, 철, 돌 곡괭이 순으로 배정하면 최소 피로도를 얻는다.
시간 복잡도
고려하는 광물 수를 L, 묶음 수를 G = ceil(L / 5)라고 하자.
- 묶음 생성:
O(L) - 묶음 정렬:
O(G log G) - 곡괭이 배정:
O(G)
전체 시간 복잡도는 O(L + G log G)이며, 공간 복잡도는 O(G)이다.
주의할 점
- 곡괭이가 부족한 경우, 남은 광물은 캐지 않으므로 처음부터
곡괭이 수 * 5개까지만 잘라야 한다. - 마지막 묶음은 광물이 5개보다 적을 수 있다. 슬라이싱으로 그대로 묶으면 별도 예외 처리 없이 계산할 수 있다.
picks를 직접 감소시키므로, 입력 배열을 보존해야 하는 환경이라면picks = picks[:]로 복사해서 사용한다.
마무리
이 문제의 포인트는 광물을 하나씩 처리하는 것이 아니라, 곡괭이의 사용 단위인 5개 묶음으로 바라보는 것이다. 묶음별 희소성을 기준으로 정렬한 뒤 좋은 곡괭이부터 배정하면 간단한 그리디 방식으로 최소 피로도를 구할 수 있다.
