[파이썬] 프로그래머스 : 광물캐기 (Lv.2)

[파이썬] 프로그래머스 : 광물캐기 (Lv.2)

 

프로그래머스

 

---

풀이

방향성 생각

한 곡괭이를 고르면 5개는 무조건 파야한다.

minerals를 5개씩 묶어서 하나의 구간으로 생각한다.

BFS를 돌리면서 곡괭이 수와 stage, stamina를 조절한다.

 

1. stage 묶기

from collections import deque

def solution(picks, minerals):
    
    arr,answer = [],[] # 5개씩 묶기
    p,q = divmod(len(minerals),5)
    for i in range(p):
        table = {'diamond':0,'iron':0,'stone':0}
        for mineral in minerals[i*5:i*5+5]:
            table[mineral] += 1
        arr.append(tuple(table.values()))    
    if q:
        table = {'diamond':0,'iron':0,'stone':0}
        for mineral in minerals[p*5:p*5+q]:
            table[mineral] += 1
        arr.append(tuple(table.values()))

5개씩 묶어야 하므로 최소 p번 돌리고 5로 나누어 떨어지지 않는 경우 나머지 q가 발생한다. 이 때 따로 추가해준다.

 

2-1. BFS

    d,i,s = picks
    q = deque([(d,i,s,0,0)]) #(다이아,철,돌,스테이지,스테미너)
    while q:
        d,i,s,stage,stamina = q.popleft()
        if (d+i+s) == 0 or stage == len(arr) : # 남은 곡괭이 0 or 끝까지 도달
            answer.append(stamina)
        else :
            x,y,z = arr[stage]
            for idx,remain in enumerate((d,i,s)):
                if remain: # 현재 곡괭이 남았으면 종류에 맞춰서 계산
                    if idx == 0 : 
                        q.append((d-1,i,s,stage+1,stamina+(x+y+z)))
                    elif idx == 1:
                        q.append((d,i-1,s,stage+1,stamina+(5*x+y+z)))
                    else :
                        q.append((d,i,s-1,stage+1,stamina+(25*x+5*y+z)))
    return min(answer)

큐에 (다이아 곡괭이,철 곡괭이, 돌 곡괭이, 스테이지, 스태미너) 순으로 넣어준다.

곡괭이를 모두 사용했거나 ( d+i+s == 0) 마지막 스테이지를 클리어 (stage == len(arr))했으면 정답 answer에 추가해준다.

ex) 테스트 케이스의 경우 minerals의 길이가 8이므로 총 2스테이지로 이루어져있다.

stage 0, stage 1을 클리어하고 다음 큐에 들어올 때 stage 2가 된다. 즉 모두 클리어했으므로 answer에 추가해준다.

 

그렇지 않은 경우에는 현재 클리어해야할 스테이지에 각 광물이 몇 개씩 있는지 확인해준다. x,y,z, = arr[stage]

곡괭이가 남아있는 경우에 곡괭이의 종류에 맞춰서 큐에 추가해준다.

 

정답 후보군 answer 중 최소값인 min(answer)을 리턴한다.

 

2-2. 브루트포스

    tools = [] # 우선순위 다이아 철 돌
    tools.extend(['diamond']*min(picks[0],len(minerals))) 
    tools.extend(['iron']*min(picks[1],len(minerals)-len(tools)))
    tools.extend(['stone']*min(picks[2],len(minerals)-len(tools)))
    case = set(P(tools,min(len(arr),len(tools))))

    for tool in case:
        temp = list(zip(tool,arr))
        stamina = 0
        for tool,mineral in temp:
            if tool == 'diamond': stamina += sum(map(lambda x,y:x*y,mineral,(1,1,1)))
            elif tool == 'iron': stamina += sum(map(lambda x,y:x*y,mineral,(5,1,1)))
            else: stamina += sum(map(lambda x,y:x*y,mineral,(25,5,1)))
        answer.append(stamina)

    return min(answer)

이 코드는 순열 생성할 때 너무 많아서 테스트케이스 24 25 33 35 시간 초과 발생

순열 생성이 아니라 다른 방법으로 하면 시간초과 안걸릴같은데 생각이 안남.

2-3. 그리디, 백트래킹

    if len(arr) > sum(picks): # 곡괭이보다 스테이지 수 많으면 다 못캠
        for i in range(len(arr)-sum(picks)):
            arr.pop()

    tools = [] # 우선순위 다이아 철 돌 순으로 곡괭이 챙김
    tools.extend(['diamond']*min(picks[0],len(minerals))) 
    tools.extend(['iron']*min(picks[1],len(minerals)-len(tools)))
    tools.extend(['stone']*min(picks[2],len(minerals)-len(tools)))
    case = list(C(tools,len(arr)))
    case.sort()
    arr.sort(key=lambda x:(-x[0],-x[1],-x[2]))

    for tool in case:
        temp = list(zip(tool,arr))
        stamina = 0
        for tool,mineral in temp:
            if tool == 'diamond': stamina += sum(map(lambda x,y:x*y,mineral,(1,1,1)))
            elif tool == 'iron': stamina += sum(map(lambda x,y:x*y,mineral,(5,1,1)))
            else: stamina += sum(map(lambda x,y:x*y,mineral,(25,5,1)))
        answer.append(stamina)

    return min(answer)

그리디로 정렬해서 풀 경우에는 곡괭이가 부족해서 캐지 못하는 부분도 정렬해서 앞으로 빠질 수 있다.

이를 제거해주고 조합을 활용해서 곡괭이 순서, 광물 캐는 순서 둘다 다이아 많은 순으로 해준다

dia iron stone 알파벳순 정렬이라 둘 다 정렬하면 된다.

---

전체코드

1. BFS

from collections import deque

def solution(picks, minerals):
    
    arr,answer = [],[] # 5개씩 묶기
    p,q = divmod(len(minerals),5)
    for i in range(p):
        table = {'diamond':0,'iron':0,'stone':0}
        for mineral in minerals[i*5:i*5+5]:
            table[mineral] += 1
        arr.append(tuple(table.values()))    
    if q:
        table = {'diamond':0,'iron':0,'stone':0}
        for mineral in minerals[p*5:p*5+q]:
            table[mineral] += 1
        arr.append(tuple(table.values()))

    d,i,s = picks
    q = deque([(d,i,s,0,0)]) #(다이아,철,돌,스테이지,스테미너)
    while q:
        d,i,s,stage,stamina = q.popleft()
        if (d+i+s) == 0 or stage == len(arr) : # 남은 곡괭이 0 or 끝까지 도달
            answer.append(stamina)
        else :
            x,y,z = arr[stage]
            for idx,remain in enumerate((d,i,s)):
                if remain: # 현재 곡괭이 남았으면 종류에 맞춰서 계산
                    if idx == 0 : 
                        q.append((d-1,i,s,stage+1,stamina+(x+y+z)))
                    elif idx == 1:
                        q.append((d,i-1,s,stage+1,stamina+(5*x+y+z)))
                    else :
                        q.append((d,i,s-1,stage+1,stamina+(25*x+5*y+z)))
    return min(answer)

 

2. 브루트포스

 

 

from itertools import permutations as P

def solution(picks, minerals):

    arr,answer = [],[] # 5개씩 묶기
    p,q = divmod(len(minerals),5)
    for i in range(p):
        table = {'diamond':0,'iron':0,'stone':0}
        for mineral in minerals[i*5:i*5+5]:
            table[mineral] += 1
        arr.append(tuple(table.values()))
    if q:
        table = {'diamond':0,'iron':0,'stone':0}
        for mineral in minerals[p*5:p*5+q]:
            table[mineral] += 1
        arr.append(tuple(table.values()))

    tools = [] # 우선순위 다이아 철 돌
    tools.extend(['diamond']*min(picks[0],len(minerals))) 
    tools.extend(['iron']*min(picks[1],len(minerals)-len(tools)))
    tools.extend(['stone']*min(picks[2],len(minerals)-len(tools)))
    case = set(P(tools,min(len(arr),len(tools))))

    for tool in case:
        temp = list(zip(tool,arr))
        stamina = 0
        for tool,mineral in temp:
            if tool == 'diamond': stamina += sum(map(lambda x,y:x*y,mineral,(1,1,1)))
            elif tool == 'iron': stamina += sum(map(lambda x,y:x*y,mineral,(5,1,1)))
            else: stamina += sum(map(lambda x,y:x*y,mineral,(25,5,1)))
        answer.append(stamina)

    return min(answer)

 

3. 그리디, 백트래킹

from itertools import combinations as C

def solution(picks, minerals):

    arr,answer = [],[] # 5개씩 묶기
    p,q = divmod(len(minerals),5)
    for i in range(p):
        table = {'diamond':0,'iron':0,'stone':0}
        for mineral in minerals[i*5:i*5+5]:
            table[mineral] += 1
        arr.append(tuple(table.values()))
    if q:
        table = {'diamond':0,'iron':0,'stone':0}
        for mineral in minerals[p*5:p*5+q]:
            table[mineral] += 1
        arr.append(tuple(table.values()))
    
    if len(arr) > sum(picks): # 곡괭이보다 스테이지 수 많으면 다 못캠
        for i in range(len(arr)-sum(picks)):
            arr.pop()
            
    tools = [] # 우선순위 다이아 철 돌 순으로 곡괭이 챙김
    tools.extend(['diamond']*min(picks[0],len(minerals))) 
    tools.extend(['iron']*min(picks[1],len(minerals)-len(tools)))
    tools.extend(['stone']*min(picks[2],len(minerals)-len(tools)))
    case = list(C(tools,len(arr)))
    case.sort()
    arr.sort(key=lambda x:(-x[0],-x[1],-x[2]))

    for tool in case:
        temp = list(zip(tool,arr))
        stamina = 0
        for tool,mineral in temp:
            if tool == 'diamond': stamina += sum(map(lambda x,y:x*y,mineral,(1,1,1)))
            elif tool == 'iron': stamina += sum(map(lambda x,y:x*y,mineral,(5,1,1)))
            else: stamina += sum(map(lambda x,y:x*y,mineral,(25,5,1)))
        answer.append(stamina)

    return min(answer)

 

 

코멘트

문제 좋은듯