프로그래머스 - 피로도

[프로그래머스] 피로도

Link

문제

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 “최소 필요 피로도”와 던전 탐험을 마쳤을 때 소모되는 “소모 피로도”가 있습니다. “최소 필요 피로도”는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, “소모 피로도”는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 “최소 필요 피로도”가 80, “소모 피로도”가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 “최소 필요 피로도”, “소모 피로도”가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• k는 1 이상 5,000 이하인 자연수입니다.
• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
  • dungeons의 가로(열) 길이는 2 입니다.
  • dungeons의 각 행은 각 던전의 [“최소 필요 피로도”, “소모 피로도”] 입니다.
  • “최소 필요 피로도”는 항상 “소모 피로도”보다 크거나 같습니다.
  • “최소 필요 피로도”와 “소모 피로도”는 1 이상 1,000 이하인 자연수입니다.
  • 서로 다른 던전의 [“최소 필요 피로도”, “소모 피로도”]가 서로 같을 수 있습니다.

입출력 예

k	dungeons	result
80	[[80,20],[50,40],[30,10]]	3

풀이

모든 경우의 수를 탐색하는 Permutation 방법이나 DFS, BFS를 활용하여 푸는 문제이다. (순서정보가 필요하기 때문에 조합문제는 아니다.)

itertools 라이브러리의 permutations 함수는 argument로 리스트와 length를 받아 리스트로 만들 수 있는 모든 length 길이의 순열을 만들어주는 함수이다.

만들 수 있는 모든 경우의 수를 만든다음에 조건을 걸고 최대 몇개의 던전을 피로도 k가지고 클리어할 수 있는지 구하면 된다.

코드는 아래와 같다.

from itertools import permutations
def solution(k, dungeons):
    max_clear = 0
    for dungeon in permutations(dungeons, len(dungeons)):
        # 이중 for loop으로 탐색
        clear = 0
        current = k
        for d in dungeon:
            # 최소 피로도 조건문
            if current >= d[0]:
                # 피로도가 d[1]만큼 까인다.
                current  -= d[1]
                if current  < 0:
                    break
                # 던전 클리어 수 + 1
                clear += 1
            else:
                break
        # 최대 던전 클리어 횟수는 dungeons의 개수보다 클 수 없으니까
        if clear == len(dungeons):
            return clear
        max_clear = max(max_clear, clear)
    return max_clear

위 방법으로도 통과할 수 있긴 하지만 순열을 활용하기 때문에 \(O(n!)\)의 시간복잡도를 가진다. (공간복잡도는 \(O(n)\))

시간복잡도를 줄이는 방법을 생각해보자

permutations 함수로 생성된 1차원 리스트들은 이런식으로 되있을 것이다.

• 첫번째 dungeon = [0, 1, 2]
• 두번째 dungeon = [0, 2, 1]

안쪽 for loop은 이 dungeon들의 요소들을 처리하는 부분인데, 이럴 경우 0을 처리하는 부분이 중복되게 된다.

이를 만약 재귀적으로 기록하면서 이미 방문했던 노드들을 재방문하지 않는 DFS나 BFS를 활용하면 시간복잡도를 줄일 수 있다.

예를들어 위에서는 [0, 1, 2]를 처리하고 [0,2,1]을 처리하지만 DFS를 사용하면 0을 처리하고 1을 처리하고 2를 처리하고, 다시 올라가서 2를 처리하고 1을 처리하게 된다.

즉 순열은 6번의 반복을 하지만 DFS 방법을 사용하면 5번의 반복만이 필요하게 된다.

DFS를 구현하는 방법에는 크게 Stack을 사용하거나 재귀함수를 사용하는 방법이 있다.

재귀함수는 어떤 값을 argument로 받을지 결정하는게 중요하다.

• 일단 이 문제의 목표가 최대 던전 clear 개수를 구하는 거니까 clear 값이 argument로 있어야한다.
• 현재의 피로도를 알아야지 다음 던전을 돌 수 있는지 없는지 결정할 수 있기 때문에 현재 피로도에 대한 argument가 필요하다.

위 두개의 argument가 있으면 현재의 피로도로 다음 던전 클리어가 가능한지를 판별하고, 클리어하고 나면 피로도를 업데이트하고 클리어 횟수를 1회 증가시키는 것을 반복하면 된다.

그리고 잊으면 안되는것이 DFS는 한번 방문했던 곳은 다시 방문하지 않기 위해 어떤 노드에 방문했는지 안했는지를 기록하는 리스트가 필요하다.

이를 전역변수로 설정하여 방문여부를 알려주면 된다.

이를 코드로 옮기면 아래와 같다.

max_clear = 0
def recur(current, clear, dungeons):
    global max_clear
    if clear > max_clear:
        max_clear = clear
    for i in range(len(dungeons)):
        if (unseen[i] == False) and current >= dungeons[i][0]:
            unseen[i] = True
            recur(current - dungeons[i][1], clear+1, dungeons)
            unseen[i] = False

def solution(k, dungeons):
    global unseen
    unseen = [False] * len(dungeons)
    recur(k, 0, dungeons)
    return max_clear

max_clear = 0
def recur(current, clear, ab, dungeons):
    global max_clear
    if clear > max_clear:
        max_clear = clear
        
    for i in range(len(dungeons)):
        # copy함수 안쓰면 안됨
        temp = ab.copy()
        if (temp[i]== False) and current >= dungeons[i][0]:
            temp[i] = True
            recur(current - dungeons[i][1], clear+1, temp, dungeons)

def solution(k, dungeons):
    len_d = len(dungeons)
    for i in range(len_d):
        unseen = [False] * len_d
        unseen[i] = True
        recur(k - dungeons[i][1], 1, unseen, dungeons)
    return max_clear