[프로그래머스 Lv2] 파이썬 - 광물 캐기

프로그래머스 - 광물 캐기

# 조건

• 마인은 곡괭이로 광산에서 광석을 캐려고 합니다.
• 마인은 다이아몬드 곡괭이, 철 곡괭이, 돌 곡괭이를 각각 0개에서 5개까지 가지고 있으며, 곡괭이로 광물을 캘 때는 피로도가 소모됩니다.
• 각 곡괭이로 광물을 캘 때의 피로도는 아래 표와 같습니다.

• 예를 들어, 철 곡괭이는 다이아몬드를 캘 때 피로도 5가 소모되며, 철과 돌을 캘때는 피로도가 1씩 소모됩니다.
• 각 곡괭이는 종류에 상관없이 광물 5개를 캔 후에는 더 이상 사용할 수 없습니다.
• 마인은 다음과 같은 규칙을 지키면서 최소한의 피로도로 광물을 캐려고 합니다.
  • 사용할 수 있는 곡괭이중 아무거나 하나를 선택해 광물을 캡니다.
  • 한 번 사용하기 시작한 곡괭이는 사용할 수 없을 때까지 사용합니다.
  • 광물은 주어진 순서대로만 캘 수 있습니다.
  • 광산에 있는 모든 광물을 캐거나, 더 사용할 곡괭이가 없을 때까지 광물을 캡니다.
• 즉, 곡괭이를 하나 선택해서 광물 5개를 연속으로 캐고, 다음 곡괭이를 선택해서 광물 5개를 연속으로 캐는 과정을 반복하며, 더 사용할 곡괭이가 없거나 광산에 있는 모든 광물을 캘 때까지 과정을 반복하면 됩니다.
• 마인이 갖고 있는 곡괭이의 개수를 나타내는 정수 배열 picks와 광물들의 순서를 나타내는 문자열 배열 minerals가 매개변수로 주어질 때, 마인이 작업을 끝내기까지 필요한 최소한의 피로도를 return 하는 solution 함수를 완성해주세요.

제한사항

• picks는 [dia, iron, stone]과 같은 구조로 이루어져 있습니다.
  • 0 ≤ dia, iron, stone ≤ 5
  • dia는 다이아몬드 곡괭이의 수를 의미합니다.
  • iron은 철 곡괭이의 수를 의미합니다.
  • stone은 돌 곡괭이의 수를 의미합니다.
  • 곡괭이는 최소 1개 이상 가지고 있습니다.
• 5 ≤ minerals의 길이 ≤ 50
  • minerals는 다음 3개의 문자열로 이루어져 있으며 각각의 의미는 다음과 같습니다.
  • diamond : 다이아몬드
  • iron : 철
  • stone : 돌

# 접근 방법

• 순열을 사용하여 모든 경우의 수를 구한다면 15!이 되므로 시간 초과가 발생할 것이다.
• 재귀를 사용한 백트래킹을 사용할 수 있을 것 같지만 다른 아이디어를 조금 고민해보았다.
  • 우선, 전체 곡괭이 개수 * 5개만큼의 인덱스만 사용해준다.
  • 돌맹이 곡괭이로 5개를 판 경우 가장 많은 피로도를 사용한다.
  • 따라서 주어지는 길이를 5개씩 짤라서 돌맹이 곡괭이로 캤을 때의 구간 피로도를 구한 후, 인덱스 번호와 함께 구간 피로도를 내림차순 정렬해준다.
  • 다이아 곡괭이의 경우 무조건 5의 피로도만 사용하므로 다이아 곡괭이를 모두 사용할 때까지 +5를 해주며 idx를 +1 씩 해준다.
  • 이후, 철 곡괭이를 사용할 건데 주어진 [구간합의 원본 인덱스 번호 * 5] : [구간합의 원본 인덱스 번호 * 5 + 5]까지 다이아의 개수를 센 후 다이아 개수 * 5 + (다이아가 아닌 광물의 개수)를 해준다.
  • 남은 것은 돌 곡괭이로 캔 피로도를 그대로 더해주면 된다.
• 또한, 마지막이 5개가 아닐 수도 있으므로 주의해주어야 한다.
  • idx가 val (5개씩 끊어서 구해 놓은 필요한 구간 개수) -1과 같다면 마지막 광물 구간이다.
  • 따라서 철 곡괭이 사용과 마찬가지로 [구간합의 원본 인덱스 번호 * 5 :]까지를 임시 리스트에 저장해준 후, 사용하는 곡괭이에 따라서 위와 같이 더해주면 된다.

def solution(picks, minerals):
    answer = 0
    # 전체 곡괭이 수 * 5 = 채굴가능한 광물의 수
    total = sum(picks) * 5                                 
    leng = len(minerals)
    # 채굴 가능한 광물의 수보다 주어진 광물이 많다면 짤라준다.
    if leng > total:
        minerals = minerals[:total]
        leng = total

    # 5개씩 끊어서 더해줄 val
    # 필요한 구간의 개수
    val = leng // 5 if leng % 5 == 0 else leng // 5 + 1
    prefix_sum = [[0, i] for i in range(val)]

    # 최악의 피로도를 가진 돌 곡괭이 기준으로 값을 더해주기
    for i in range(0, val):
        for j in range(i * 5, i * 5 + 5):
            if j < leng:
                if minerals[j] == 'diamond':
                    prefix_sum[i][0] += 25
                elif minerals[j] == 'iron':
                    prefix_sum[i][0] += 5
                else:
                    prefix_sum[i][0] += 1

    # 구간 합 기준으로 정렬해준다.
    prefix_sum.sort(key=lambda x: x[0], reverse=True)
    idx = 0
    while idx < val:
        # 마지막 구간의 경우 5개가 아닐수도 있으므로 temp에 임시 저장하여 구해준다.
        if prefix_sum[idx][1] == val - 1:
            # 길이가 더 긴 경우 미리 잘라냈으므로 슬라이싱 끝 부분을 비워주워도 무방하다.
            temp = minerals[prefix_sum[idx][1] * 5:]
            if picks[0]:
                answer += len(temp)
                picks[0] -= 1
            elif picks[1]:
                for mineral in temp:
                    if mineral == 'diamond':
                        answer += 5
                    else:
                        answer += 1
                picks[1] -= 1
            else:
                answer += prefix_sum[idx][0]

        else:
            if picks[0]:
                answer += 5
                picks[0] -= 1
            elif picks[1]:
                for mineral in minerals[prefix_sum[idx][1] * 5:prefix_sum[idx][1] * 5 + 5]:
                    if mineral == 'diamond':
                        answer += 5
                    else:
                        answer += 1
                picks[1] -= 1
            else:
                answer += prefix_sum[idx][0]
                picks[2] -= 1

        idx += 1

    return answer