[프로그래머스] 광물 캐기 (Python)

문제 요약

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

조건

1. picks 배열에 [다이아,철,돌] 형태로 곡괭이 개수가 주어짐 (각 0 ~ 5)
2. minerals 배열에 캘 광물들의 이름이 순서대로 주어짐 (5 ~ 50)
3. 광물을 순서대로 캘 때, 하나의 곡괭이로 연속 5개의 광물을 캐면 더 이상 사용 불가
4. 광물이나 곡괭이가 없다면 종료
5. 사용하는 곡괭이와 캐는 광물에 따라서 위 표와 같이피로도가 소모됨

최소한의 피로도 반환하는 문제

접근

1. 가장 먼저 하나의 곡괭이 당 5개의 광물을 캘 수 있으니 minerals 배열을 앞에서부터 순서대로 5개로 묶었다.
2. (다이아,철,돌) 순으로 곡괭이를 사용하기로 했고, 최소한의 피로도를 위해 광물들의 묶음도 곡괭이 사용 순서대로 내림차순 정렬해주었다.
   여기서 발생한 문제 → 곡괭이 수가 부족해서 캘 수 없는 광물들까지 5개 묶음에 포함하게 되면, 캐지면 안되는 광물이 먼저 캐어지는 문제가 발생한다. 광물은 순서대로 캐야하기 때문에 캘 수 있는 광물만 sorting에 포함시켜야 한다. 따라서 곡괭이가 캘 수 있는 광물들만 포함하도록 minerals 배열을 잘라주었다.
3. (다이아,철,돌) 순서로 정렬된 광물 묶음을 곡괭이와 매치시켜 피로도를 계산했다.
   -  idx == 사용한 곡괭이수의 누적 개수
   -  idx가 dia보다 작으면 다이아 곡괭이 사용
   -  idx가 dia+iron 보다 작으면 철 곡괭이 사용 → iron이라고 해서 처음에 틀렸었다.

코드

def solution(picks, minerals):
    answer = 0

    # (곡괭이 총합 x 5) 만큼 캘 수 있는 광물의 수만큼 minerals 리스트 자르기
    summ = sum(picks) * 5
    if summ < len(minerals):
        minerals = minerals[:summ]

    # 광물 5개씩 그룹으로 묶기
    group = []
    tmp = [0, 0, 0] # 묶음에서 [다이아,철,돌]의 개수
    cnt = 0
    for i in range(len(minerals)):
        if minerals[i] == "diamond":
            tmp[0] += 1
        elif minerals[i] == "iron":
            tmp[1] += 1
        else:
            tmp[2] += 1

        cnt += 1

        # 5개를 다 묶었거나, 마지막 묶음인데 5개보다 작을 때 group 배열에 추가 
        if cnt == 5 or i == len(minerals) - 1:
            group.append(tmp)
            tmp = [0, 0, 0]
            cnt = 0

    # 피로도 계산
    group.sort(reverse=True)

    dia, iron, stone = picks
    for idx in range(len(group)):
        d, i, s = group[idx]

        if idx < dia:
            answer += d + i + s
        elif idx < dia + iron:
            answer += d * 5 + i + s
        else:
            answer += d * 25 + i * 5 + s
        idx += 1

    return answer

 

완전탐색으로 푸는 방법도 있다.

...