[프로그래머스] 피로도

문제

 

 

풀이

완전 탐색 알고리즘을 구상해야겠다고 생각이 들어서, 이중 for문을 사용해 해결했다. break를 활용해 피로도가 부족하면 바로 도는걸 중지하도록 하여 시간을 조금 줄여봤다.

from itertools import permutations

def solution(k, dungeons):
    #0 ~ 던전의 개수 - 1까지 모든 값을 가지는 순열 모두 반환
    orders = list(permutations(range(len(dungeons))))
    
    
    max_dungeon_cnt = 0
    #모든 던전 가는 경우의 수 순회
    for order in orders :
        my_tired = k
        current_dungeon_cnt = 0
        
        #던전 돌기
        for dungeon_idx in order :
            if my_tired >= dungeons[dungeon_idx][0] :
                current_dungeon_cnt += 1
                my_tired -= dungeons[dungeon_idx][1]
            else:
                break
        #다 돌았으면 max_dungeon count 갱신
        max_dungeon_cnt = max(max_dungeon_cnt, current_dungeon_cnt)
    
    return max_dungeon_cnt

 

풀이 로직

1. python 내장 메소드인 permutations 활용하여 0 ~ 던전의 개수 -1 까지 모든 경우의수 순열을 뽑는다

2. 던전을 가는 모든 경우의 수 리스트(orders)를 순회하기 시작한다(order 튜플의 값들은 던전 순서)

3. order에 있는 dungeon의 인덱스들을 순서대로 도는데, 던전 입장이 가능하면 현재 cnt를 + 1 해주고, 입장이 불가하면 break한다.

4. 마지막 까지 던전을 돌던, 피로도가 부족해서 못돌던 간에 max_dungeon_cnt를 갱신해준다

 

 

※permutations 메소드

itertools 모듈의 함수로, 가능한 모든 순열을 만들어준다.

사용법 : 

from itertools import permutations

permutations(iterable, r)

 

iterable : 순열을 만들 대상(리스트, range 등)

r : 뽑을 개수, 생략 시 전체 길이로 순열 생성

 

 

Github Link  ←

BackJoon-Programmers/프로그래머스/2/87946. 피로도 at main · jaeheonki/BackJoon-Programmers