[프로그래머스 / 피로도 / python]

오늘의 1솔 ♬

오늘의 문제는 프로그래머스의 Lv.2 피로도 !
바로 풀고 싶다면 요기로 → 문제 바로가기

문제 설명

문제 요약

1. 게임에서 오늘 탐험할 수 있는 던전의 목록이 주어진다

2. 각 던전은 두 가지 요소를 가지고 있다

   • 필요 HP: 탐험을 시작하기 위해 요구되는 최소 HP
   • 소모 HP: 던전 탐험에 소모되는 HP
     문제에는 피로도라고 표현되어 있는데 HP라고 읽는 게 이해가 더 쉽다

3. 게임 유저는 하루 동안 최대한 많은 던전을 탐험하고 싶다

4. 유저가 하루 동안 탐험할 수 있는 최대 던전 수를 구하라
   
   

변수 설명

	의미	데이터 형식	길이
k	유저의 초기 HP	자연수 1 ~ 5000	1
dungeons	탐험 가능한 던전 목록	[필요 HP, 소모 HP] 형태의 요소로 이루어진 리스트 각 HP는 1 ~ 1000	1 ~ 8

풀이

아래의 방식으로 풀어야겠다고 생각했다

1. 각 던전을 탐험하는 순서를 전부 구한 다음
2. 그 순서대로 던전을 조회하며
3. 최대 던전 수를 업데이트 한다

탐색 관련해서 블로그를 찾아보다가 이 방법이 순열을 이용한 방법이라는 걸 알게 되었다

이와 관련해서 itertools라는 라이브러리가 있다고 해서 요걸 사용해봤다

import itertools


def solution(k, dungeons):
    answer = 0
    len_dungeons = len(dungeons)

    # 1
    sequences = list(itertools.permutations([i for i in range(0, len_dungeons)]))

    # 2
    for i in range(len(sequences)):
        hp = k
        possible_dungeons = 0

        # 3
        for j in range(len_dungeons):
            this_dungeon = dungeons[sequences[i][j]]

            # 4
            if hp >= this_dungeon[0]:
                possible_dungeons += 1
                hp -= this_dungeon[1]
            else:
                break

        # 5
        if possible_dungeons > answer:
            answer = possible_dungeons
            # 6
            if answer == len_dungeons:
                break

    return answer

# 1

itertools의 permutations 모듈을 사용해 던전을 돌 순서를 모두 구한 다음 sequences에 저장한다
permutations 모듈의 사용 방법은 아래와 같다

itertools.permutations(배열, 조합할 원소 개수)

첫 번째 파라미터로는 0 ~ 던전 수-1까지의 수를 가진 배열을 넣었다
dungeons의 인덱스 값이라고 생각하면 된다

두 번째 파라미터는 설정하지 않았다
설정하지 않으면 자동으로 첫 번째 파라미터의 원소 전부를 상대로 순열을 구한다

그 다음 이 값을 list 형식으로 변환해줘야 한다
변환하지 않으면 인덱스로 접근할 수 없다
리스트 변환 전 후 출력해보면 차이가 요로케

# 2

던전을 도는 순서를 전부 구했으니 각 순서대로 돌아보자 !
새로운 순서로 돌 때마다 HP와 방문한 던전 수를 초기화 해준다

# 3

순서에 정해진대로 던전을 돈다
i는 순열로 구한 던전 조회 순서 중 i번째 조합이라는 뜻
j는 그 i번째 조합에서 j번째로 도는 던전이라는 뜻
따라서 this_dungeon은 i 번째 순서 조합에서 j 번째로 도는 던전이라는 의미이다

# 4

만약 현재 HP가 필요 HP 이상이면 이 던전을 탐험할 수 있다 !
이 경우 소모 HP만큼 HP를 감소시키고 방문한 던전 수를 증가시킨다

반대로 현재 HP가 필요 HP보다 부족하다면 ?
더이상 이 순서대로 던전을 돌 수 없다는 뜻이기 때문에 반복문을 탈출한다

# 5

자 이렇게 i번째 순서 조합에 따라 던전을 돌았다
탐험을 진행한 던전의 수가 기존 최대값(answer)보다 크다면 이를 갱신한다

# 6

요거는 추가로 설정한 탈출 조건인데
만약 i번째 순서 조합대로 던전을 돌았는데 그 수가 전체 던전의 수와 같다면 이보다 큰 값은 나올 수 없기 때문에 더이상 진행할 필요가 없으니 반복문을 탈출하게 했다

음 근데 ...

왼쪽이 탈출 조건 설정한 코드, 오른쪽이 설정 안 한 코드인데 큰 차이는 없었다 ㅎ
오히려 설정한 게 더 오래 걸린 경우도 심심찮게 있고 그러네 ? 하핫

새로 배운 내용

• 리스트 선언과 동시에 값을 설정하고 싶다면 아래처럼

new_list = [i for i in range(number)]

• 알고리즘 내용은 아니지만 파이참 파일 이름 변경할 때 [ Refactor ] - [ Rename ]으로 들어가면 된다 ...
  내 노트북 Fn키 없는데 ... 모두 단축키만 알려줘서 슬펐어 ...
  
  

마무리

이 문제의 카테고리는 완전탐색
... 지금까지 탐색 문제는 성공률도 가장 낮고 흥미도 없어서 늘 회피해왔다
하지만 ... 언제까지고 회피할 수는 없으니까 ...
울면안돼


그래도 오늘도 한 문제 풀었다

앞으로도 힘내렴