[프로그래머스] 피로도. 다양한 구현과 괴수 코드 분석

다양한 전체 순회

permutation

• 가장 간단하게 순열을 사용할 수 있다.

from itertools import permutations

def solution(k, dungeons):

    mx = 0
    for perm in permutations(dungeons, len(dungeons)):
        hp = k
        visit = 0
        for need,cost in perm:
            if(hp >= need):
                visit+=1
                hp-=cost
            else:
                break
        mx = max(mx,visit)
    return mx

Permutation 직접 구현

• 직접 permutation을 구현할 수도 있다.

def solution(k, dungeons):
    def makePerm(make,last):
        if(len(last)==0):
            perms.append(make)
            return
        else:
            for i in range(len(last)):
                makePerm(make+[last[i]],last[:i]+last[i+1:])
    
    perms = []
    makePerm([],dungeons)
    
    mx = 0
    for perm in perms:
        # 이하 생략

DFS

• 외판원 순회 문제로 볼 수도 있다.
• 중간에 backtracking도 넣을 수 있어 더 성능이 좋을 것으로 보인다.

def solution(k, dungeons):
    
    visit=[False]*len(dungeons)
    def dfs(k,cnt,dungeons):
        if(cnt>=len(dungeons)):
            return cnt
        result = cnt
        for i in range(len(dungeons)):
            need, cost = dungeons[i]
            if(visit[i]==False and k>=need):
                visit[i] = True  #visit 상태를 전달하지 않고 True, False만 Toggle
                result = max(result, dfs(k-cost,cnt+1,dungeons))
                visit[i] = False
        return result

    mx = dfs(k,0,dungeons)
    
    return mx

그리고 괴수

윤응구님의 응근하지만은 않은 코드

solution = lambda k, d: max([solution(k - u, d[:i] + d[i+1:]) + 1 for i, (m, u) in enumerate(d) if k >= m] or [0])

• solution 자체를 재귀로 만들었다.
• 위의 Permutation 직접 구현과 구조가 비슷하다.
  • 이미 방문한 dungeon은 목록에서 뺀다.
  • 방문하면서 피로도는 감소시켜준다.
  • permutation 중 피로도 조건에 맞는 던전만 자귀한다.
  • 베이스 케이스를 위해 or [0] 을 통해 0 부터 방문수를 더해갈 수 있도록 했다.
• 코드를 잘 타일러보면 아래와 같은 의미인 걸 알 수 있다.

def solution(k, dungeons):
	if not dungeons:
		return 0
	result = 0
	for i in range(len(dungeons)):
		need,cost = dungeons[i]
		if(k>=need):
			visitedDungeons = solution(k-cost,dungeons[:i]+dungeons[i+1:])+1
			result = max(result, visitedDungeons)
	return result

• 마지막에 쓴 DFS에서 cnt 파라미터를 없애기 위해, dungeons 배열을 바꿔서 전달해주고 cnt를 0에서부터 거꾸로 썼다는 차이가 있다.
• dfs 코드에서도 dungeons 파라미터는 제거해 줄 수 있다. (외부 스코프에서 가져옴)