[프로그래머스][C++] 피로도

피로도

문제 링크

피로도

분석

모든 던전 순서를 다 시도해봐야 합니다.

예시 1번처럼 던전이 3개라면, 탐색 순서는 $3! = 6$입니다.

• A > B > C
• A > C > B
• B > A > C
• B > C > A
• C > A > B
• C > B > A

즉, 모든 경우의 수를 시도하려면 순열을 사용하면 됩니다.

다른 방법으로 깊이 우선 탐색(DFS)을 사용하는 방법이 있습니다.
깊이 우선 탐색은 한 경로를 끝까지 탐색한 후, 백트래킹하며 새로운 경로를 탐색합니다.
스택이나 재귀를 사용하여 구현합니다.

풀이

순열을 사용하는 방법입니다.

#include <vector>
#include <algorithm>

using namespace std;

int solution(int k, vector<vector<int>> dungeons) {
    int answer = -1;
    
    // 순열을 사용하기 위해 정렬을 해야합니다.
    sort(dungeons.begin(), dungeons.end());
    
    do {
        int currentFatigue = k; // 현재 피로도
        int count = 0;  // 탐험한 던전 수
        
        for (int i = 0; i < dungeons.size(); ++i)
        {
            // 탐험이 가능한 경우
            if (currentFatigue >= dungeons[i][0])
            {
                currentFatigue -= dungeons[i][1];
                ++count;
            }
        }
        
        answer = max(answer, count);
        
    }while (next_permutation(dungeons.begin(), dungeons.end())); // 순열 생성
    
    return answer;
}

---

DFS를 사용한 방법입니다.

#include <vector>

using namespace std;

int res;

int dfs(vector<vector<int>>& dungeons, int k, int count, vector<bool>& visited)
{
    // 탐험 할 수 있는 최대 던전수
    res = max(res, count);
    
    for(int i = 0; i < dungeons.size(); i++)
    {
        // 이미 탐험 했거나 탐험 할 수 없는 경우
        if (visited[i] || dungeons[i][0] > k) continue;
        
        // 탐험 한 던전
        visited[i] = true;
        dfs(dungeons, k - dungeons[i][1], count + 1, visited);
        // 다른 경로를 탐색 할 수 있도록 원래대로 되돌린다
        visited[i] = false;
    }
    
    return res; 
}

int solution(int k, vector<vector<int>> dungeons) {
    vector<bool> visited(dungeons.size(), false);
    
    int answer = dfs(dungeons, k, 0, visited);
    
    return answer;
}

성능 요약

순열을 사용한 성능입니다.

시간 복잡도는 $O(n! \times n)$입니다.

• 알고리즘 헤더의 정렬 함수 $O(n \ log \ n)$
• 모든 순열 탐색 $O(n!)$
• 각 순열에서 던전을 탐색하는 반복문 $O(n)$
• $O(n \ log \ n + n! \times n)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 1 〉 통과 (0.01ms, 4.15MB)
테스트 2 〉 통과 (0.01ms, 4.21MB)
테스트 3 〉 통과 (0.01ms, 4.16MB)
테스트 4 〉 통과 (0.01ms, 4.15MB)
테스트 5 〉 통과 (0.03ms, 4.16MB)
테스트 6 〉 통과 (0.08ms, 4.15MB)
테스트 7 〉 통과 (0.73ms, 4.16MB)
테스트 8 〉 통과 (1.39ms, 4.14MB)
테스트 9 〉 통과 (0.02ms, 4.15MB)
테스트 10 〉 통과 (0.12ms, 4.14MB)
테스트 11 〉 통과 (0.01ms, 3.71MB)
테스트 12 〉 통과 (0.55ms, 4.21MB)
테스트 13 〉 통과 (0.92ms, 4.21MB)
테스트 14 〉 통과 (1.22ms, 4.17MB)
테스트 15 〉 통과 (1.12ms, 4.15MB)
테스트 16 〉 통과 (0.13ms, 3.63MB)
테스트 17 〉 통과 (0.95ms, 4.15MB)
테스트 18 〉 통과 (0.01ms, 4.14MB)
테스트 19 〉 통과 (0.01ms, 4.23MB)

---

DFS를 사용한 성능입니다.

시간 복잡도는 $O(n! \times n)$입니다.

• 재귀 호출 횟수 $O(n!)$
• 함수 안의 반복문 $O(n)$
• $O(n! \times n)$

공간 복잡도는 $O(n)$입니다.

• 던전 개수만큼의 visited $O(n)$
• 재귀 호출 스택 $O(n)$
• $O(n + n)$

테스트 1 〉 통과 (0.01ms, 4.13MB)
테스트 2 〉 통과 (0.01ms, 4.21MB)
테스트 3 〉 통과 (0.01ms, 4.21MB)
테스트 4 〉 통과 (0.02ms, 4.44MB)
테스트 5 〉 통과 (0.03ms, 4.21MB)
테스트 6 〉 통과 (0.09ms, 4.02MB)
테스트 7 〉 통과 (0.48ms, 4.01MB)
테스트 8 〉 통과 (1.17ms, 3.68MB)
테스트 9 〉 통과 (0.01ms, 3.64MB)
테스트 10 〉 통과 (0.04ms, 4.21MB)
테스트 11 〉 통과 (0.01ms, 3.67MB)
테스트 12 〉 통과 (0.08ms, 3.63MB)
테스트 13 〉 통과 (0.02ms, 4.21MB)
테스트 14 〉 통과 (0.01ms, 4.14MB)
테스트 15 〉 통과 (0.01ms, 4.2MB)
테스트 16 〉 통과 (0.01ms, 4.13MB)
테스트 17 〉 통과 (0.01ms, 4.16MB)
테스트 18 〉 통과 (0.01ms, 4.14MB)
테스트 19 〉 통과 (0.01ms, 4.21MB)