피로도

https://programmers.co.kr/learn/courses/30/lessons/87946

코딩테스트 연습 - 12주차

 

참고 : https://comdoc.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%88%9C%EC%97%B4%EA%B3%BC-%EC%A1%B0%ED%95%A9

파이썬 순열과 조합

 

순열을 이용한 전수조사(brute force)...

from itertools import permutations


def solution(k, dungeons):
    answer = 0
    for permutation in permutations(dungeons):
        count, health = 0, k
        for required_health, consumed_health in permutation:
            if health >= required_health:
                health -= consumed_health
                count += 1
            else:
                break
        answer = max(answer, count)
    return answer

테스트 1 〉	통과 (0.03ms, 10.1MB)
테스트 2 〉	통과 (0.03ms, 10.2MB)
테스트 3 〉	통과 (0.05ms, 10.3MB)
테스트 4 〉	통과 (0.08ms, 10.1MB)
테스트 5 〉	통과 (0.42ms, 10.3MB)
테스트 6 〉	통과 (3.54ms, 10.3MB)
테스트 7 〉	통과 (39.58ms, 10.2MB)
테스트 8 〉	통과 (42.90ms, 10.2MB)
테스트 9 〉	통과 (0.05ms, 10.2MB)
테스트 10 〉	통과 (2.65ms, 10.1MB)
테스트 11 〉	통과 (0.02ms, 10.2MB)
테스트 12 〉	통과 (24.17ms, 10.1MB)
테스트 13 〉	통과 (13.83ms, 10.3MB)
테스트 14 〉	통과 (13.10ms, 10.1MB)
테스트 15 〉	통과 (12.60ms, 10.2MB)
테스트 16 〉	통과 (1.62ms, 10.3MB)
테스트 17 〉	통과 (13.25ms, 10.2MB)
테스트 18 〉	통과 (0.01ms, 10.3MB)
테스트 19 〉	통과 (0.05ms, 10.2MB)

 

직접 순열을 만들면
만드는 과정에서
답을 찾을 수 있기 때문에
효율적입니다. 

def solution(k, dungeons):
    def dfs(count, health, visited):
        nonlocal answer
        for i, (need_tired, use_tired) in enumerate(dungeons):
            if not visited[i] and need_tired <= health:
                visited[i] = True
                dfs(count + 1, health - use_tired, visited)
                visited[i] = False
        answer = max(answer, count)

    answer = 0
    dfs(0, k, [False for _ in range(len(dungeons))])
    return answer

테스트 1 〉	통과 (0.03ms, 10.1MB)
테스트 2 〉	통과 (0.05ms, 10.1MB)
테스트 3 〉	통과 (0.02ms, 10.2MB)
테스트 4 〉	통과 (0.22ms, 10.1MB)
테스트 5 〉	통과 (0.93ms, 10.2MB)
테스트 6 〉	통과 (2.78ms, 10.1MB)
테스트 7 〉	통과 (15.61ms, 10.2MB)
테스트 8 〉	통과 (41.47ms, 10.3MB)
테스트 9 〉	통과 (0.03ms, 10.1MB)
테스트 10 〉	통과 (0.88ms, 10.2MB)
테스트 11 〉	통과 (0.01ms, 10.1MB)
테스트 12 〉	통과 (1.99ms, 10.2MB)
테스트 13 〉	통과 (0.25ms, 10.1MB)
테스트 14 〉	통과 (0.09ms, 10.3MB)
테스트 15 〉	통과 (0.07ms, 10.3MB)
테스트 16 〉	통과 (0.04ms, 10.1MB)
테스트 17 〉	통과 (0.17ms, 10.3MB)
테스트 18 〉	통과 (0.02ms, 10.2MB)
테스트 19 〉	통과 (0.07ms, 10MB)

 

자바

class Solution {
    int[][] dungeons;
    int answer = 0;

    void dfs(int tired, boolean[] check, int cnt) {
        for (int i = 0; i < dungeons.length; i++)
            if (!check[i] && dungeons[i][0] <= tired) {
                check[i] = true;
                dfs(tired - dungeons[i][1], check, cnt + 1);
                check[i] = false;
            }
        answer = Math.max(answer, cnt);
    }

    public int solution(int k, int[][] dungeons) {
        this.dungeons = dungeons;
        dfs(k, new boolean[dungeons.length], 0);
        return answer;
    }
}

테스트 1 〉	통과 (0.14ms, 78.9MB)
테스트 2 〉	통과 (0.03ms, 74.2MB)
테스트 3 〉	통과 (0.03ms, 76.6MB)
테스트 4 〉	통과 (0.15ms, 78.7MB)
테스트 5 〉	통과 (0.49ms, 82.1MB)
테스트 6 〉	통과 (0.54ms, 74.9MB)
테스트 7 〉	통과 (1.30ms, 77.2MB)
테스트 8 〉	통과 (2.56ms, 77.4MB)
테스트 9 〉	통과 (0.05ms, 73.3MB)
테스트 10 〉	통과 (0.43ms, 74.3MB)
테스트 11 〉	통과 (0.09ms, 77.6MB)
테스트 12 〉	통과 (0.49ms, 82.7MB)
테스트 13 〉	통과 (0.12ms, 79.8MB)
테스트 14 〉	통과 (0.07ms, 77MB)
테스트 15 〉	통과 (0.05ms, 78.1MB)
테스트 16 〉	통과 (0.06ms, 79.4MB)
테스트 17 〉	통과 (0.06ms, 77.8MB)
테스트 18 〉	통과 (0.11ms, 77.1MB)
테스트 19 〉	통과 (0.06ms, 68MB)