[programmers] 피로도

Gomao·2023년 3월 27일
0

코딩테스트 준비

목록 보기
15/20

프로그래머스 Lv.2 피로도

문제 분석
1. 각 던전의 입장 제한 피로도와 소모 피로도가 담긴 배열이 주어진다(dengeons)
2. 총 제한 피로도가 주어진다(k)
3. 이때 가장 많은 던전을 탐험할 수 있는 방법은 몇 가지 던전을 탐험 가능할까?

뭔가 익숙한 주제이다. 예전에 하던 게임중에 이런 시스템이 있었다.
그 게임의 피로도 시스템은 이렇게 코딩되어 있었겠구나.ㅋㅋ

문제 접근
1. 주제가 완전탐색이어서 DFS/BFS를 사용할 지 반복문을 사용할 지 정해야 한다.
2. 그런데 DFS는 아직 익숙하지가 않았다. (초기 배치를 어떻게 해야 할 지..)
3. dengeons 배열을 순서 있게 정렬한 후에, 각 경우에 대해 모두 탐색한다.

생각해볼 문제
1. 완전탐색을 하지 않고도 해답을 구할 수 있는 방법이 있을까?
2. 모든 순열에 대해 탐색을 한다면 복잡도가 지나치게 높아지지 않을까?
3. DFS방식과 순열탐색 방식은 효율 측면에서 얼마나 차이가 날까?

작성한 코드
아무튼 코드를 작성 해보았다. 아무래도 파이썬이다 보니 이 방식이 가장 편해보였다.

from itertools import permutations as perm
def solution(k, dungeons):

    clear = 0
    way = list(perm(dungeons,len(dungeons)))
    for arr in way:
        tired = k
        cleared = 0
        for j in arr:
            if tired >= j[0]:
                tired -= j[1]
                cleared += 1
        if clear < cleared:
            clear = cleared

    return clear

응? 생각보다 효율성이 좋다
아무래도 dengeons의 길이가 짧기 때문일까?

하지만 그래도 DFS로 푸는 방법도 알아야 한다.
왜 why?
JavaScript에는 import permutations이 없으니까.....

따라서 이 포스팅에서는 javascript로 permutations을 구현하는 방법과,
DFS를 통해서 푸는 방법을 모두 다룰 예정이다.

다른 사람의 풀이 - DFS

answer = 0
N = 0
visited = []

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

코드를 한번 해석 해보자.
1. dfs부분

0-1. 전역변수로 선언된 visited 배열은 dengeons의 길이만큼 0으로 채워놓은 배열이다.
0-2. 전역변수로 선언된 N은 dengeons의 길이이다.
1. dfs 함수는 피로도, count, dengeons배열을 요소로 받는다.
2. dangeons의 길이만큼 탐색을 시도한다.
	3-1) 피로도가 dunjeons의 입장 제한 피로도보다 높고, 방문한 적이 없다면
    3-2) visited[j] = 1 ...이건 왜?
    3-3) 피로도는 dunjeons의 소모 피로도만큼 감소, count는 +1하여 재귀함수 호출
    3-4) visited[j] = 0 ...이건 왜?
4. 전역변수로 선언된 answer에 대해서, cnt가 answer보다 크면 값을 교체해준다.
  1. solution부분
1. N, visited를 전역변수로 선언한다. (위의 0-1, 0-2로 설명 하였음)
2. 선언한 dfs함수를 호출한다
3. 최종적으로 남아있는 answer 값을 정답으로 제출한다.

다른 부분은 직관적으로 이해가 되는데,
dfs부분의 3-2, 3-4에 visited[j]를 활용한 부분이 살짝 이해가 가지 않는다.

visited를 1로 바꿔주고 재귀를 실행해주고 재귀가 끝나면 visited를 0으로 돌려주고?

효율성 비교

DFS의 시간복잡도 : O(n2)O(n^2)
permutations의 시간복잡도 : O(n!)O(n!)
dfs를 조금 더 연습해야 할 것 같다...

--------------------------------아래 코드 출처 링크--------------------------------

번외 - JavaScript의 순열 구현

 const getPermutations = function (arr, selectNumber) {
    const results = [];
    if (selectNumber === 1) return arr.map((el) => [el]); 

    arr.forEach((fixed, index, origin) => {
      const rest = [...origin.slice(0, index), ...origin.slice(index+1)] 
      const permutations = getPermutations(rest, selectNumber - 1); 
      const attached = permutations.map((el) => [fixed, ...el]); 
      results.push(...attached); 
    });

    return results;
}

번외 - JavaScript의 조합 구현

const getCombinations = function (arr, selectNumber) {
    const results = [];
    if (selectNumber === 1) return arr.map((el) => [el]); 

    arr.forEach((fixed, index, origin) => {
      const rest = origin.slice(index + 1); 
      const combinations = getCombinations(rest, selectNumber - 1); 
      const attached = combinations.map((el) => [fixed, ...el]); 
      results.push(...attached); 
    });

    return results;
}
profile
코딩꿈나무 고마오

0개의 댓글