광물캐기(프로그래머스) 문제풀이

문제 

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

프로그래머스

 

 

 

문제 접근 방식

광산에 다이아, 철, 돌이 존재하며 이를 캘 수 있는 곡괭이가 주어지며, 곡괭이의 속성에 따라 광물을 캘 때의 피로도가 달라진다. 곡괭이보다 단단한 광석을 캐면 피로도가 빨리 쌓이게 된다는 특징이 있다. 즉, 아래와 같은 특징을 가지는 그리디 문제라고 판단하고 문제를 접근했다.

최대한 단단한 광물이 많이 나올 때, 단단한 곡괭이를 사용한다

 

 

위의 아이디어를 사용한 처리과정은 아래와 같다.

1. 광물을 5개의 단위(page)로 쪼개고, 각 부분에 대해서 광물의 개수 [다이아,철,돌] 을 구한다
>> ex. [(1,3,1), (4,0,1), ...]

2. 단단한 광물이 많은 부분에 대해 단단한 곡괭이를 사용한다. 
이를 위해 단단한 광물이 많은 부분을 먼저처리할 수 있도록 정렬한다( 다이아>철 순으로 내림차순 정렬)
>> ex. pages=[(4,0,1),(1,3,1), ...]

3. 정렬된 페이지를 순회하며 단단한 곡괭이로 광물을 캐면 최소 피로도를 구할 수 있다.

 

 

위

 

 

시간 복잡도

알고리즘 내에서 정렬을 하기 때문에 O(NlogN)의 시간이 걸리며, 광물의 최대 길이가 50이기 때문에 시간 내에 동작한다

 

코드

from collections import deque

def solution(picks, minerals):
    n=sum(picks)
    pages=[]
    
    # 각 곡괭이를 통해 광물을 캘때의 피로도를 담는다. 마지막 부분에서 피로도를 계산할 때 사용한다
    # (곡괭이,광물)
    fatigue=dict({
        ("dia","dia"):1,("dia","iron"):1,("dia","stone"):1,
        ("iron","dia"):5,("iron","iron"):1,("iron","stone"):1,
        ("stone","dia"):25,("stone","iron"):5,("stone","stone"):1,
    })
    
    # 5개의 단위(page)로 나눠서, 각 페이지의 광물 개수 [다이아,철,돌]를 구한다
    for i in range(n):
        dia=iron=stone=0
        s=5*i
        if s>=len(minerals):
            break
        for j in range(5):
            if s+j>=len(minerals):
                break
            if minerals[s+j]=="diamond":
                dia+=1
            elif minerals[s+j]=="iron":
                iron+=1
            else:
                stone+=1
        pages.append((dia,iron,stone))
    
    # 페이지 정렬 (단단한 광물이 많은 순으로 내림차순 정렬)
    pages.sort(key=lambda x:(-x[0],-x[1]))
    
    answer=0
    
    # 곡괭이를 다이아>철>돌 순으로 담아준다
    q=deque(["dia"]*picks[0]+["iron"]*picks[1]+["stone"]*picks[2])
    
    # 페이지를 순회하며 큐에서 곡괭이를 꺼내 광물을 캐고 피로도를 구한다
    for d,i,s in pages:
        pick=q.popleft()
        value=d*fatigue[(pick,"dia")]+i*fatigue[(pick,"iron")]+s*fatigue[(pick,"stone")]
        answer+=value
        
        
    return answer

 

 

 

회고

문제가 그리디이기는 신경써야되는 부분들이 존재한다. 

1. 광물 또는 곡괭이를 먼저 다 사용한 경우
>> 곡괭이의 개수를 기준으로 광물 리스트를 순회하며, 만약 곡괭이 개수*5가 광물의 범위를 넘어서면 break
>> 이후 페이지 개수만큼만 순회를 하여, 앞부분부터 처리하는 것과 같은 처리 가능

2. 각 광물에 대한 곡괭이의 피로도 부분을 어떤 자료구조를 사용할 것인지
>> 딕셔너리 자료형을 사용하여 (곡괭이,광물)키로 각 피로도에 접근

3. 곡괭이를 하나씩 처리할 때 어떻게 할 것인지 
>> 큐를 사용해서 명령어처럼 사용