Lv.2 피로도

코딩테스트 연습 - 피로도 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

A2 팀원들끼리 함께 풀어본 오늘의 문제.

 

카테고리부터 완전탐색인만큼 그에 맞게 풀어보았다.

 

마침 어제 BFS, DFS를 공부했는데,

적을 것이 너무 많아서 정리하지도 못했다.

바쁘다 바빠

 

이번 문제는 알짜배기니까

완전탐색에 대해 공부하신 분들이라면  먼저 풀어보시는 것이 좋을 것 같다.

 

1. BFS 풀이법 (deque)

# BFS를 이용한 문제풀이
# deque 사용
# queue 개념과 BFS 개념 인지 필요

from collections import deque

def solution(k, dungeons):
    answer = 0
    queue = deque()
    # queue에 튜플 (k, route)를 넣어줌. route : 다녀온 던전 Index 리스트
    queue.append((k, []))

    #queue가 비어있을 때까지 반복
    while queue:
        k, route = queue.popleft() # queue의 맨 앞의 것을 뺌 << queue의 특징
        for i in range(len(dungeons)):
            (a, b) = dungeons[i] # a : 최소필요피로도 b : 소모피로도
            if k >= a and i not in route: # 조건 인지 필요, print(queue)하면 이해가 빠를 듯
                temp = route + [i]
                queue.append((k - b, temp))
            else:
                answer = max(answer, len(route))

    return answer

 

2. DFS 풀이법 (Backtracking)

# Backtracking, DFS 사용

answer = 0
N = 0
visited = []

# global로 전역변수 설정
# 이는 변수가 함수 외부에서도 접근 가능하고, 함수 내부에서도 값을 수정할 수 있음
# 가능한 모든 던전 탐험 경로를 탐색

def dfs(k, cnt, dungeons):
    global answer
    if cnt > answer:
        answer = cnt

    for j in range(N):
        if k >= dungeons[j][0] and not visited[j]:
            visited[j] = 1
            dfs(k - dungeons[j][1], cnt + 1, dungeons)
            visited[j] = 0


def solution(k, dungeons):
    global N, visited
    N = len(dungeons)
    visited = [0] * N
    dfs(k, 0, dungeons)
    return answer

 

3. itertools - permutation (팀원 스승호님의 풀이)

itertools를 쓰면 매우 코드 짜는 게 간편해져서 보기 좋은 것 같다.

from itertools import permutations

def solution(k, dungeons):
    answer = []
    for dungeon_list in permutations(dungeons):
        count = 0
        hp = k
        for dungeon in dungeon_list:
            if hp >= dungeon[0]:
                hp -= dungeon[1]
                count+=1
                if count == len(dungeons):
                    return count
        else:
            answer.append(count)
    return max(answer)

 

4. itertools - premutation + lambda (팀원 단아님의 풀이)

아이디어가 좋은 코드

from itertools import *

def solution(k, dungeons):
    # 던전을 들어가는 순서를 담은 순열
    dungeon_datadic = {}
    dungeon_dataset = list(permutations(dungeons, len(dungeons)))
    for number in range(len(dungeon_dataset)):
        dungeon_datadic[number] = 0 
		# print(dungeon_datadic) #{0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}
    # print(dungeon_dataset[0]) #([80, 20], [50, 40], [30, 10])
    # print(dungeon_dataset[0][0]) # [80, 20]


    #데이터 셋은 모든 경우의 수를 포함하고 있으므로, 맨 앞에서부터 시도하여 dic의 각 위치에 시도 횟수 더해주기
    for key, value in dungeon_datadic.items():
        hp = k #very good!
        for length in range(len(dungeons)):
            if hp >= dungeon_dataset[key][length][0]:
                dungeon_datadic[key] += 1
                hp = hp - dungeon_dataset[key][length][1]
            else:
                break

    answer = sorted(dungeon_datadic.items(), key=lambda x: x[1], reverse=True) #내림차순 정렬
    return answer[0][1]