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

 

 

 

🌱 문제

프로그래머스

• 작업을 끝내기까지 필요한 최소한의 피로도를 구하는 문제
• 광물을 모두 캐거나 곡갱이를 모두 사용하면 작업 끝남
• 어떤 광물을 어떤 곡갱이로 캐는지에 따라 소모되는 피로도가 다름
• 하나의 곡갱이로 5개의 광물을 캘 수 있음

 

🌱 풀이1 완전 탐색 → 시간 초과

처음에는 곡갱이(picks)의 개수가 최대 15개 이고, 광물(minerals)의 길이는 최대 50이라 완전탐색으로 풀 수 있겠다고 생각하였습니다. 왜냐하면 곡갱이 1개당 광물 5개를 캘 수 있으므로 최대로 필요한 곡갱이 수는 10개입니다. 또, 곡갱이 종류는 3개이므로 모든 곡갱이 순서의 경우의 수는 최대 $3^{10} = 59049$ 라고 생각하여 완전 탐색으로 풀이를 하였는데, 4개의 테스트 케이스에서 시간 초과가 터졌습니다. (왜 시간 초과가 발생했는지 아직 모르겠음,,ㅜㅜ)

# 시간 초과 코드
def solution(picks, minerals):
    answer = 0

    n = len(minerals) // 5
    if len(minerals) % 5 != 0:
        n += 1

    pick_list = []
    pick_list += ['dia' for _ in range(picks[0])]
    pick_list += ['iron' for _ in range(picks[1])]
    pick_list += ['stone' for _ in range(picks[2])]

    answer = 25 * 50

    if len(pick_list) < n:
        n = len(pick_list)

    for pick in set(permutations(pick_list, n)):
        tiredness = 0
        minerals_ = deepcopy(minerals)
        for p in pick:
            for _ in range(5):
                if minerals_:
                    tiredness += table[p][mineral_dict[minerals_.pop(0)]]

        if tiredness < answer:
            answer = tiredness

    return answer

 

 

🌱 풀이2 구현

주어진 표를 조금만 자세히 보면 완전 탐색을 하지 않고도 최소한의 피로도를 구할 수 있다는 것을 알 수 있다. 왜냐하면 표에서 다이아몬드 곡갱이가 가장 적은 피로도를 소모하고 돌 곡갱이가 가장 많은 피로도를 소모하기 때문에, 가장 많은 피로도를 소모하는 광물들을 가장 적은 피로도를 소모하는 곡갱이 순서대로 매핑(?)해주면 된다. 즉, 가장 피로도를 많이 소모하는 광물과 가장 피로도를 적게 소모하여 광물을 캘 수 있는 곡갱이를 매핑!

1. 캘 수 있는 광물의 개수

# 캘 수 있는 광물의 개수
n = min(len(minerals), sum(picks) * 5)

먼저 캘 수 있는 광물의 개수를 카운트합니다. 광물을 모두 캐거나 곡갱이를 모두 사용하면 작업 끝나므로 광물의 개수와 곡갱이의 개수 * 5 중에 더 작은 값이 캘 수 있는 광물의 개수가 됩니다.

 

2. 광물 조사

mineral_count = []
tmp = []
for idx in range(n):
    if idx % 5 == 0:  # 5개마다 초기화
        if tmp:
            mineral_count.append(tmp)
        tmp = [0, 0, 0]

    if minerals[idx] == "diamond":
        tmp[0] += 1
    elif minerals[idx] == "iron":
        tmp[1] += 1
    else:
        tmp[2] += 1
    if idx == n - 1:
        mineral_count.append(tmp)
        break

곡갱이 하나 당 광물을 5개씩 캘 수 있으므로 주어진 광물들을 5개씩 묶어서 [diamond 개수, iron 개수, stone 개수] 형태로 저장합니다.
mineral이 ["diamond", "diamond", "diamond", "iron", "iron", "diamond", "iron", "stone"]인 경우, 5개씩 묶으면
[["diamond", "diamond", "diamond", "iron", "iron"], ["diamond", "iron", "stone"]] 으로 묶이고,
mineral_count는 [[3, 2, 0], [1, 1, 1]]이 담깁니다.

 

3. 피로도를 많이 필요로하는 순서대로 광물을 정렬

mineral_count.sort(key=lambda x: (x[0], x[1], x[2]), reverse=True)

피로도를 많이 소모하는 광물 순서대로 정렬합니다. diamons → iron → stone 순으로 피로도를 많이 소모하므로 diamond가 가장 많은 묶음, 그리고 iron이 많은 묶음 순서대로 정렬합니다. sort() 메서드의 key 인자와 reverse 인자를 지정해서 정렬할 수 있습니다. 

 

4. 피로도 계산

while mineral_count:
    mineral = mineral_count.pop(0)
    if picks[0] > 0:
        answer += mineral[0] * 1 + mineral[1] * 1 + mineral[2] * 1
        picks[0] -= 1
    elif picks[1] > 0:
        answer += mineral[0] * 5 + mineral[1] * 1 + mineral[2] * 1
        picks[1] -= 1
    else:
        answer += mineral[0] * 25 + mineral[1] * 5 + mineral[2] * 1
        picks[2] -= 1

정렬된 순서대로 차례로 다이아몬드 곡갱이, 철 곡갱이, 돌 곡갱이를 사용하여 캐면 됩니다. 피로도는 표에서 준 값으로 계산합니다.

 

🌱 정답 코드

def solution(picks, minerals):
    answer = 0

    # 캘 수 있는 광물의 개수
    if len(minerals) <= sum(picks) * 5:
        n = len(minerals)
    else:
        n = sum(picks) * 5

    mineral_count = []
    tmp = []
    for idx in range(n):
        if idx % 5 == 0:  # 5개마다 초기화
            if tmp:
                mineral_count.append(tmp)
            tmp = [0, 0, 0]

        if minerals[idx] == "diamond":
            tmp[0] += 1
        elif minerals[idx] == "iron":
            tmp[1] += 1
        else:
            tmp[2] += 1
        if idx == n - 1:
            mineral_count.append(tmp)
            break

    mineral_count.sort(key=lambda x: (x[0], x[1], x[2]), reverse=True)

    while mineral_count:
        mineral = mineral_count.pop(0)
        if picks[0] > 0:
            answer += mineral[0] * 1 + mineral[1] * 1 + mineral[2] * 1
            picks[0] -= 1
        elif picks[1] > 0:
            answer += mineral[0] * 5 + mineral[1] * 1 + mineral[2] * 1
            picks[1] -= 1
        else:
            answer += mineral[0] * 25 + mineral[1] * 5 + mineral[2] * 1
            picks[2] -= 1

    return answer