[Programmers] 광물 캐기(Python, Javascript)

문제

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

프로그래머스

 

 

---

풀이

Python

(시간초과 오답)

from itertools import permutations
def solution(picks, minerals):
    d = {'diamond' : 0, 'iron':1, 'stone':2}
    fatigue = [[1, 1, 1], [5, 1, 1], [25, 5, 1]]
    lst = []
    
    for i in range(3):
        for j in range(picks[i]):
            lst.append(i)
            
    perm = permutations(lst)
    answer = 25*len(minerals)
    
    for p in perm:
        t, i, stop = 0, 0, False
        for j in p:
            for k in range(5):
                if i == len(minerals):
                    stop = True
                    break
                t += fatigue[j][d[minerals[i]]]
                i += 1
            if stop:
                break
        answer = min(answer, t)
    
    return answer

 

(정답)

재귀로 할까 하다가 어떤 걸 어디로 배치해야 할지 모르는데 재귀가 불가능하다 싶어서 고민했다.

값이 제일 적게 나올 수 있도록 다이아몬드가 많은 곳에 다이아몬드 곡괭이를 둬야 하니까

그리디로 풀어야 한다는 힌트를 얻었다.

 

8펀 테케만 틀려서 뭐가 문제일까 했는데, 곡괭이 개수만큼 광물을 다섯개씩 묶어줘야 풀린다.

def solution(picks, minerals):
    fatigue = [[1, 1, 1], [5, 1, 1], [25, 5, 1]]
    
    lst = []
    dia, iron, stone = 0, 0, 0
    for i in range(sum(picks)):
        dia, iron, stone = 0,0,0
        for j in range(i*5, (i+1)*5):
            if j >= len(minerals):
                break
                
            if minerals[j] == 'diamond':
                dia += 1
            elif minerals[j] == 'iron':
                iron += 1
            else:
                stone += 1
        lst.append((dia, iron, stone))
        
    lst.sort(key = lambda x: (x[0], x[1], x[2]))
    
    i, answer = 0, 0
    while lst and i < 3:
        while picks[i] != 0 and lst:
            picks[i] -= 1
            t = lst.pop()
            
            for j in range(3):
                answer += fatigue[i][j] * t[j]
        i += 1
    return answer

 

Javascript

자바스크립트에서 sort 다중 비교 하는 것을 배웠다.

function solution(picks, minerals) {
    var answer = 0;
    
    const n = picks[0] + picks[1] + picks[2];
    const fatigue = [[1, 1, 1], [5, 1, 1], [25, 5, 1]]
    let lst = [];
    
    for (let i=0; i < n;i++){ 
        if (i*5 > minerals.length) break
        
        let [dia, iron, stone] = [0, 0, 0];
        for (let j = i*5; j < (i+1)*5; j++){  
            if (minerals[j] == 'diamond'){
                dia += 1;
            } else if (minerals[j] == 'iron'){
                iron += 1;
            } else if (minerals[j] == 'stone') {
                stone += 1;
            }
        }
        lst.push([dia, iron, stone]);
    }
    
    lst.sort((a, b) => {
        return a[0] - b[0] || a[1] - b[1] || a[2] - b[2]
    })
    
    let i = 0;
    while (lst.length > 0 && i < 3){
        while (picks[i] != 0 && lst.length > 0) {
            t = lst.pop();
            for (let j=0; j<3; j++){
                answer += fatigue[i][j] * t[j]
            }
            picks[i] -= 1;
        }
        i += 1
    }
    
    return answer;
}