[Java] Programmers 위클리챌린지12주차_피로도(Level 2) (순열)

문제출처: https://programmers.co.kr/learn/courses/30/lessons/87946

코딩테스트 연습 - 12주차

 

문제이해

 

목표

유저의 현재피로도: k
각 던전별 정보: dungeons[i][]
 - 2번째배열의 첫번째값[0]: 최소 피로도
 - 2번째배열의 두번째값[1]: 소용 피로도 

위 정보를 가지고 유저가 탐험할수 있는 최대 던전 수를 구하시오

 

풀이

 

첫번째 풀이.

순열로, 던전을 도는 순서의 모든 case를 찾아서(탐색후), 돌 수 있는 던전만 count하여 정답을 갱신 

 

두번째 풀이.

똑같이 순열로, 던전을 도는 순서를 찾는데, 돌 수 있는 던전인지를 미리미리 count해서  순서를 찾음
그리고 answer보다 더 큰 count를 answer에 갱신

첫번째 풀이는 순열을 만드는 비용, 던전을 count 하는 비용이 각각듦
하지만, 두번째 풀이는 순열을 만들때 던전을 count하기 때문에 순열을 만드는 비용만 든다. 

 

소스코드

첫번째 풀이코드

class Solution {
    private int answer;
    private int K;
    private int[][] dgs;
    private boolean[] visited;
    private int[] list;

    public int solution(int k, int[][] dungeons) {
        answer = 0;
        K = k;
        dgs = dungeons;
        visited = new boolean[dungeons.length];
        list = new int[dungeons.length];

        // 순열 탐색 시작
        dfs(0);
        return answer;

    }

    private void dfs(int depth) {
        if (depth == dgs.length) {
            int k = K;
            int count = 0;
            for (int d : list) {
                if (k >= dgs[d][0]) { // 던전 돌 수 있음
                    k -= dgs[d][1];
                    count++;
                } 
            }
            answer = Math.max(answer, count);
            return;
        }

        for (int i = 0; i < dgs.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                list[depth] = i;
                dfs(depth + 1);
                visited[i] = false;
            }
        }
    }
}

 

두번째 풀이 코드

public class 프로그래머스_위클리챌린지_12주차_피로도 {
    private int answer;
    private int[][] dgs;
    private boolean[] visited;
    private int[] list;

    public int solution(int k, int[][] dungeons) {
        answer = 0;
        dgs = dungeons;
        visited = new boolean[dungeons.length];
        list = new int[dungeons.length];

        // 순열 탐색 시작
        dfs(0, k, 0);
        return answer;

    }

    private void dfs(int depth, int k, int count) {
        for (int i = 0; i < dgs.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                if (k >= dgs[i][0]) { // 돌수 있는 던전이면 돌고 count++
                    k -= dgs[i][1];
                    list[depth] = i;
                    dfs(depth + 1, k, count + 1);
                    k += dgs[i][1];
                } else { // 못도는 던전임 count 그대로
                    dfs(depth + 1, k, count);
                }
                visited[i] = false;
            }
        }
        if (count > answer) {
            answer = count;
        }
    }
}

 

결과

미리미리 count하는 두번째 풀이가 조금 더 성능이 좋다.