[프로그래머스] Level2 : 피로도[Python]

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

프로그래머스

 

제한 사항 :

• k는 1 이상 5,000 이하인 자연수입니다.
• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
  • dungeons의 가로(열) 길이는 2 입니다.
  • dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
  • "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
  • "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
  • 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

풀이 :

1. 제한 사항에서 dungeons의 개수가 1이상 8이하 이므로 순열을 이용한 완전탐색 알고리즘을 사용하기로함

-> 순열 사용 이유 - 던전 개수가 8개일 경우 최대 시간복잡도가 8! = 40320 이므로 시간초과가 발생하지 않으므로

2. 경우의 수마다 탐험할 수 있는 던전 수를 세기 위한 변수 temp와 k를 임시로 저장할 temp_k변수 초기화

3. 각 경우의 수마다 던전 수만큼 반복(내부 반복문)하여 k 보다 p[ i ][ j ][ 0 ]이 작거나 같다면

-> 최소 필요 피로도를 만족하므로 k에서 소모 피로도를 감소, temp + 1

4. 현재 경우의 수의 temp 값이 answer 보다 클 경우

-> answer = temp로 교체

 

* Tip - itertools 라이브러리의 permutations 메소드를 사용하면 순열을 for문으로 직접 구현하지 않아도 됨

itertools 라이브러리에 대해 알고 싶다면? - https://decordray.tistory.com/30

 

코드 :

from itertools import permutations

def solution(k, dungeons):
    answer = -1
    p = permutations(dungeons,len(dungeons)) # 순서를 고려한 모든 경우의 수를 확인해봐야 하므로 순열 생성
    p = list(map(list,p))   # permutations 메소드 사용시 튜플형태로 저장이 되는데 이를 리스트 형태로 바꿔줌(안해줘도 됨)
    
    for i in range(len(p)): # 순서를 고려한 모든 경우의 수 만큼 탐색
        temp = 0                        # 경우의 수마다 탐험할 수 있는 던전 수를 세기 위한 변수
        temp_k = k                      # 경우의 수마다 k를 임시로 저장할 temp_k 변수
        for j in range(len(dungeons)):  # 던전 수 만큼 반복
            if p[i][j][0] <= temp_k:    # k보다 p[i][j][0]이 작거나 같으면 최소 필요 피로도를 만족하므로 
                temp_k -= p[i][j][1]    # k에서 소모 피로도를 감소시킨 후
                temp += 1               # temp + 1
        if temp > answer:               # 현재 경우의 수의 temp 값이 answer 보다 크다면 answer = temp로 교체
            answer = temp

    return answer