광물 캐기

날짜 : 2023. 10. 14

사용 언어 : python

 

문제

 

코드

def solution(picks, minerals):
    check = list()  # 우선순위 리스트
    pick = picks[0] + picks[1] + picks[2]
    if len(minerals) > pick * 5:  # 현재 있는 곡괭이로 캘 수 없는 광물들 생략
        minerals = minerals[:pick * 5]
    for i in range(0, len(minerals), 5):
        tmp = 0
        for j in range(i, i + 5):
            if j not in range(len(minerals)): break
            if minerals[j] == "diamond": tmp += 25
            elif minerals[j] == "iron": tmp += 5
            else: tmp += 1
        check.append([i // 5, tmp])
    check.sort(key = lambda x : -x[1])  # 피로도 큰 순서로 정렬
    
    res = 0
    now = 0  # 현재 곡괭이
    
    flag = True
    for t in range(len(check)):
        while True:
            if now > 2: 
                return res
            if picks[now] == 0: 
                now += 1  # 다 썼는지 체크
            else:
                break
        idx = check[t][0] * 5
        for i in range(idx, idx + 5):
            if i not in range(len(minerals)): 
                break  # 범위 체크
            if now == 0:  # 다이아 곡괭이
                res += 1
            elif now == 1:  # 철 곡괭이
                if minerals[i] == "diamond": res += 5
                else: res += 1
            else:  # 돌 곡괭이
                if minerals[i] == "diamond": res += 25
                elif minerals[i] == "iron": res += 5
                else: res += 1
        picks[now] -= 1  # 사용 후 차감
        
    return res

 

 

풀이

- 곡괭이는 한개에 5개의 광물만 캘 수 있고, 각 곡괭이마다 광물별로 소모되는 피로도는 상이하다.

- 그래서 우선 곡괭이가 한정되어 있기 때문에 캘 수 없는 광물들부터 슬라이싱하여 삭제한다.

- 이후 한 곡괭이에 5개씩 캘 수 있고, 요구되는 피로도가 달라진다는 점을 활용해 5개씩 묶어 피로도를 설정하고, 해당 인덱스와 피로도를 묶은 후 check 리스트에 넣는다.

- check 리스트는 인덱스별로 오름차순으로 정렬되어 있기 때문에 요구 피로도의 내림차순으로 정렬한다.

- 그 다음 각 곡괭이별로 돌려가면서 광물별 피로도를 계산한다.

- 다만 곡괭이가 중간에 부족한 경우도 발생할 수 있기 때문에 해당 케이스의 예외사항도 넣는다.

 

 

알게된 점

- 광물별로 묶어서 그리디로 풀면 되는 줄 아는 문제였지만 꽤나 고민할 부분이 많았던 문제였다.

- 우선 곡괭이 사용 순서가 다이아 -> 철 -> 돌 순서였는데 다이아를 사용하다가 다 사용해서 곧바로 돌로 사용하는 케이스(철 곡괭이가 없어서 바로 넘어가는 경우)를 고려하지 못했다는 점이 첫 번째 실수였다.

- 그 다음은 테스트케이스 8이었는데, 애초부터 곡괭이가 부족해 채광을 할 수 없는 것들을 날려야 피로도를 정렬하는데 있어서 결과값에 이상이 발생하지 않는 다는 점을 잊었다.

- 이 부분은 프로그래머스 질문 글들을 통해서 확인할 수 있었고, if len(minerals) > pick * 5 ~ 부분을 추가하게 되었다.

- 테스트케이스 8 전까지는 무난하게 풀었지만 그 부분을 고려하지 못해서 좀 많은 고민을 했었던 것 같다.

 

 

 

참고 사이트

-