프로그래머스 피로도 - python

알고리즘은 여태 찍먹하면서 공부했지만 각잡고 공부를 시작한지는 이제 막 하루다.

 

각설하고, 이번 알고리즘 문제는 프로그래머스의 완전탐색 문제다.

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

프로그래머스

 

처음 문제를 접했을 때, 

최소피로도 - 소모피로도를 기준으로 정렬하여 풀면 된다고 생각했다.

def solution(k, dungeons):
    answer = 0
    
    for i in range(len(dungeons)):
        a = dungeons[i][0] - dungeons[i][1]
        dungeons[i].append(a)
    
    arr = sorted(dungeons,key=lambda x: -x[2])
    
    for i in range(len(arr)):
        if k >= arr[i][0]:
            k = k- arr[i][1]
            answer += 1
    return answer

처음 생각해낸 코드는 잘 동작하였지만, 몇몇개의 테스트케이스에서 실패했다.

 

몇십분을 더 고민한 끝에 검색했고, 대부분 순열을 이용한 해결법이 나왔다.

 

from itertools import permutations

def solution(k, dungeons):
    answer = 0
    p = permutations(dungeons, len(dungeons))
    for i in p:
        count = 0
        hp = k
        for j in i:
            if j[0] <= hp:
                hp-= j[1]
                count += 1
        if count > answer:
            answer = count
    return answer

 

여기서 처음보는 모듈을 발견했다.

permutations 모듈은 첫번째 인자로 조합을 짤 list를, 두 번째 인자로는 몇 개로 조합을 이룰지 Number를 적는 인자다.

(둘 모두 안적으면 오류)

permutations 모듈을 이용한 이후에는 1차원적으로 생각한 그대로 적으면 문제가 풀린다.

 

문제를 푼 이후에 내 문제점을 생각해냈다.

 

첫번째. 문제가 완전탐색임에도 그리디로 풀었다는 점.

내가 처음 생각해낸 코드의 반례는 찾지 못한 것이 아쉽다.

 

두 번째. dangerous의 최대 length를 생각하지 못하고 순열을 생각해내지 못했다는 점.

단순히 모든 조합을 하나하나 짠다는 것은 비효율적이라 생각했기에 전혀 생각조차 하지 못했었다.