[홀로 하는 코딩 공부] 광물 캐기(Python)

프로그래머스

사용 언어: Python

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/172927#

프로그래머스

 

*** 본 문제를 푸는 과정을 공유하려 한다.

---

▶ 문제에서 피로도가 누적됨에 따라 합산되는 값 중 최소 값을 구한다는 것을 보자마자 DFS 구현을 떠올렸다. 처음에는 아래와 같이 작성해보았다. 

mins = {'diamond': 0, 'iron': 1, 'stone': 2}
tired = [[1, 1, 1], [5, 1, 1], [25, 5, 1]]
answer = []
def dfs(picks, minerals, total):
    if sum(picks) == 0:
        answer.append(total)
        return
    for i, pick in enumerate(picks):
        if picks[i] == 0:
            continue
        else:
            picks[i] -= 1
            print(picks)
            cur_total = 0
            cnt = 0
            for mineral in minerals:
                cur_total += tired[i][mins[mineral]]
                cnt += 1
                if cnt == 5:
                    break
            if cnt == 5:
                dfs(picks, minerals[5:], total + cur_total)
                picks[i] += 1
            else:
                answer.append(total+cur_total)
                return
                
    
def solution(picks, minerals):
    dfs(picks, minerals, 0)
    print(answer)
    return min(answer)

 

 

 

▶ 반례를 생각해보려해도 떠오르지않아서  Ref_1을 참고하여 아래의 입력값을 넣어보았다. answer 배열에 55만 저장된다. 코드를 다시 보니 picks에 다이아몬드, 철, 돌 순으로 입력되고 코드는 다이아몬드가 0이 아닌 이상 다이아몬드부터 소모하도록 되어있었다. 하지만 아래의 입력값으로는 돌 -> 다이아몬드 순으로 소비해야 최솟값을 얻을 수있는 케이스였다. 그래서 dfs를 부르기 전 solution 함수에서 다이아몬드부터 시작하는 경우, 철부터 시작하는 경우, 돌부터 시작하는 경우 각각을 고려한 부분을 코드로 재구성하였다.

mins = {'diamond': 0, 'iron': 1, 'stone': 2}
tired = [[1, 1, 1], [5, 1, 1], [25, 5, 1]]
answer = []

def calc_minerals(i, minerals):
    cur_total = 0
    cnt = 0
    for mineral in minerals:
        cur_total += tired[i][mins[mineral]]
        cnt += 1
        if cnt == 5:
            break
    return cnt, cur_total

def dfs(picks, minerals, total):
    if sum(picks) == 0:
        answer.append(total)
        return
    for i, pick in enumerate(picks):
        if picks[i] == 0:
            continue
        else:
            picks[i] -= 1
            cnt, cur_total = calc_minerals(i, minerals)
            if cnt == 5:
                dfs(picks, minerals[5:], total + cur_total)
                picks[i] += 1
            else:
                answer.append(total+cur_total)
                picks[i] += 1
                return
                
def solution(picks, minerals):
    for i in range(3):
        if picks[i] > 0:
            picks[i] -= 1
            cnt, cur_total = calc_minerals(i, minerals)
            if cnt == 5:
                dfs(picks, minerals[5:], cur_total)
                picks[i] += 1
            else:
                answer.append(cur_total)

    return min(answer)

 

▶ 통과다. 그런데 테스트24에서 시간이 많이 걸리는게 마음에 걸린다. 해당 부분의 시간을 줄이고자 코드를 다시 본다. 다시 보니, 추후에 누적되는 값 계산 중 answer 배열에 저장되어있는 값보다 많으면 더 이상 dfs를 할 필요가 없다. 그러므로 answer 어떠한 값이라도 있다면 answer의 마지막 값하고 현재 누적 값(=total)하고 비교해서 total이 더 크다면 return한다. 그러면 시간면에서 훨씬 더 단축될 것이다. 그리고 이렇게 하면 answer에 저장되는 값도 적으니 solution함수에서 return 할 때 사용되는 min함수 내 계산에서도 시간적으로 단축될 것이라고 생각되었다.

mins = {'diamond': 0, 'iron': 1, 'stone': 2}
tired = [[1, 1, 1], [5, 1, 1], [25, 5, 1]]
answer = []

def calc_minerals(i, minerals):
    cur_total = 0
    cnt = 0
    for mineral in minerals:
        cur_total += tired[i][mins[mineral]]
        cnt += 1
        if cnt == 5:
            break
    return cnt, cur_total

def dfs(picks, minerals, total):
    if answer:
        if answer[-1] < total:
            return
    if sum(picks) == 0:
        answer.append(total)
        return
    for i, pick in enumerate(picks):
        if picks[i] == 0:
            continue
        else:
            picks[i] -= 1
            cnt, cur_total = calc_minerals(i, minerals)
            if cnt == 5:
                dfs(picks, minerals[5:], total + cur_total)
                picks[i] += 1
            else:
                answer.append(total+cur_total)
                picks[i] += 1
                return
                
def solution(picks, minerals):
    for i in range(3):
        if picks[i] > 0:
            picks[i] -= 1
            cnt, cur_total = calc_minerals(i, minerals)
            if cnt == 5:
                dfs(picks, minerals[5:], cur_total)
                picks[i] += 1
            else:
                answer.append(cur_total)

    return min(answer)

 

 

▶ 테스트24의 경우 152.06ms -> 3.31ms, 테스트25의 경우 132.42ms -> 1.20ms로 많이 단축된 것을 확인할 수 있다.

▶ 반면, 반례까지 생각하는 실력은 여전히 부족하다.

 

Ref_1) https://school.programmers.co.kr/questions/48123

프로그래머스

---

>> 위 내용은 필자가 코딩테스트 문제를 푼 코드입니다.

>> 부족한 점이 많을 수 있기에 잘못된 내용이나 궁금한 사항이 있으면 댓글 달아주시기 바랍니다.

>> 긴 글 읽어주셔서 감사합니다.