Lv2. 피로도

문제 보기 :  피로도

프로그래머스

---

문제

• 정답률 : 60%

---

작성 코드

## 오류 발생 코드
def solution(k, dungeons):

    for i in range(len(dungeons)):
        kk = dungeons[i]
        kk.append(kk[0]-kk[1])
    dungeons.sort(key= lambda x:x[2],reverse=True)
    
    answer = 0
    for d in dungeons:
        if k >= d[0]:
            k -= d[1]
            answer +=1
    return answer

암튼 여러번 수정을 해봤는데도 계속 안풀려서 이 참에 완전 탐색을 공부도 해볼겸 정석대로 해보기로 했다.

• 참고한 사이트 : [Python / 알고리즘] 완전탐색 : 소수찾기 (프로그래머스) — 코딩으로 세계정복 (tistory.com)

[Python / 알고리즘] 완전탐색 : 소수찾기 (프로그래머스)

---

from itertools import permutations

def solution(k, dungeons):
    answer = 0
    d = list(permutations(dungeons,len(dungeons))) #[[30,10],[80,20],[50,40]]
    for i in range(len(d)):
        dd= d[i]
        an = 0
        remain = k
        for tt in dd:
            if remain >= tt[0]:
                remain -= tt[1]
                an +=1
        if answer < an:
            answer = an
    return answer

---

풀이

데이터 분석을 할 때 itertools을 몇번. 정말 손에 꼽을 정도로 써봤던거 같은데 이번에 정말 용도를 발견하게 됨...

주로 집합 만들 때 사용하는 것 같고 함수 앞에 list, set 등등 데이터 유형을 설정하면 바로 그 형태로 만들어준다는게 너무 편해서 여태 안 썼던게 억울할 정도..

이 문제는 dungeons 내 리스트들을 섞을 수 있을만큼 최대한 섞어서 사용할 수 있는 던전 수를 구하는 문제다.
리스트 구조는 [최소 필요정도, 소모정도]이며, k는 현재 피로도다.

​

예제)

k=8, dungeons=[[7, 3], [5, 4], [1, 1]], result=3
→ [7,3] 기준으로 8>7이므로 3을 소모하고 해당 던전을 탐험할 수 있다. (남은 피로도 5, 던전 1)
→ [5,4] 기준으로 5>=5이므로 4를 소모하고 해당 던전을 탐험할 수 있다. (남은 피로도 1, 던전 2)
→ [1,1] 기준으로 1>=1이므로 1를 소모하고 해당 던전을 탐험할 수 있다. (남은 피로도 0, 던전 3)
∴ 탐험한 던전은 3개다.

​

k=10, dungeons=[[9, 2], [10, 3], [7, 3], [5, 4], [1, 1]], result=4
→ [9, 2] 기준으로 10>9이므로 2을 소모하고 해당 던전을 탐험할 수 있다. (남은 피로도 8, 던전 1)
→ [10,3] 기준으로 8<10이므로 2을 소모할 수 없고 해당 던전을 탐험할 수 없다. (남은 피로도 8, 던전 1)
→ [7,3] 기준으로 8>7이므로 3을 소모하고 해당 던전을 탐험할 수 있다. (남은 피로도 5, 던전 2)
→ [5,4] 기준으로 5>=5이므로 4을 소모하고 해당 던전을 탐험할 수 있다. (남은 피로도 1, 던전 3)
→ [1,1] 기준으로 1>=1이므로 1을 소모하고 해당 던전을 탐험할 수 있다. (남은 피로도 0, 던전 4)
∴ 탐험한 던전은 4개다.

permutations으로 생성한 dungeons 순열 중 [[10, 3], [9, 2], [7, 3], [5, 4], [1, 1]]도 같은 방법으로 확인해볼 수 있다.

​

그럼 이제 마지막으로 순열/조합 집합에 만드는 itertools의 함수들을 정리한 뒤 포스팅을 마무리한다

#순열/조합 함수들은 모두 튜플이 반환 값이다. 

#일반순열 
permutations(iterable, n) 

#중복순열
product(iterable, repeat=num) 

#조합
combinations(iterable, n) 

#중복조합 
combinations_with_replacement(iterable객체, n) 

#중복이 없는 list 
set() 

#map 함수 : list의 모든 요소에 함수를 적용하고 iterable로 반환한다 
map(lambda x : 적용함수, iterable)