[PGM_87946] 피로도 (java)

문제링크

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

코딩테스트 연습 - 피로도

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 완전탐색(순열)

1. 문제 이해

- 던전을 도는 xx게임은 피로도를 소모하게된다. 던전에 대한 피로도는 최소피로도와 소모피로도가 있다. 최소 피로도는 던전을 돌기위한 최소의 피로도이며 소모피로도는 던전을 돌았을 때 소모되는 피로도이다.

 

던전들의 최소피로도 그리고 소모피로도에 대한 값의 정보와 피로도가 주어졌을 때 유저가 최대 몇개의 던전을 돌 수 있는지 알아보자.  던전은 한번씩만 돌 수있다.

 

2. 접근방법

- 순열로 던전을 도는 순서를 모두 탐색하는 방법으로 접근하였다. 던전을 도는 순서에 대한 모든 순열을 구하여 던전을 직접 돌고, 가장 많이 던전을 도는 방법을 알아보았다.

 

3. 세부 해결방안

//순열의 다음 위치를 찾아주기
private boolean nextPermutation(int[] numbers){
    int prevIndex;
    int n = numbers.length;
    int nextIndex = n-1;
    int changeIndex = -1;

    for(int i = n-2; i >= 0; i--){
        prevIndex = nextIndex;
        nextIndex = i;

        if(numbers[nextIndex] < numbers[prevIndex]){
            changeIndex = nextIndex;
            break;
        }
    }

    if(changeIndex == -1)
        return false;

    for(int i = n-1; i > changeIndex; i--){
        if(numbers[i] > numbers[changeIndex]){
            swap(numbers, i, changeIndex);
            break;
        }
    }
    while(++changeIndex < --n){
        swap(numbers,changeIndex,n);
    }
    return true;
}

//배열의 순서변경
private void swap(int[] numbers, int a, int b){
    int temp = numbers[a];
    numbers[a] = numbers[b];
    numbers[b] = temp;
}

Permutation은 오름차순 -> 내림차순으로 이동하면서 찾을 수 있도록 해주었다. 만약 모든 수가 내림차순이라면 더이상 변경할 값이 없기 때문에 순열을 모두 탐색했다고 할 수 있다.

 

//정해진 순서로 던전을 입장했을 때 입장한 던전의 수
public int doDungeons(int[] permutation, int[][] dungeons, int p){
    int count = 0;
    for(int i = 0; i < permutation.length; i++){
        //피로도가 던전입장을 위한 최소 피로도보다 작은경우
        if(dungeons[permutation[i]][0] <= p){
            p -= dungeons[permutation[i]][1];
            count++;
        }
    }
    return count;
}

정해진 순서로 던전에 대한 피로도와 비교해 실제로 입장할 수 있는 던전의 수를 리턴받게 하였다.

 

구현코드

package pgm_87946;

public class Solution {
    public int solution(int k, int[][] dungeons) {
        int[] permutation = new int[dungeons.length];
        for(int i = 0; i < permutation.length; i++){
            permutation[i] = i;
        }
        int max = 0;
        do{
            //모든 경우에 대해 던전을 돌고 최대값을 찾아준다.
            int count = doDungeons(permutation, dungeons, k);
            max = max > count ? max : count;
        }while (nextPermutation(permutation));
        return max;
    }

        //정해진 순서로 던전을 입장했을 때 입장한 던전의 수
        public int doDungeons(int[] permutation, int[][] dungeons, int p){
            int count = 0;
            for(int i = 0; i < permutation.length; i++){
                //피로도가 던전입장을 위한 최소 피로도보다 작은경우
                if(dungeons[permutation[i]][0] <= p){
                    p -= dungeons[permutation[i]][1];
                    count++;
                }
            }
            return count;
        }

    //순열의 다음 위치를 찾아주기
    private boolean nextPermutation(int[] numbers){
        int prevIndex;
        int n = numbers.length;
        int nextIndex = n-1;
        int changeIndex = -1;

        for(int i = n-2; i >= 0; i--){
            prevIndex = nextIndex;
            nextIndex = i;

            if(numbers[nextIndex] < numbers[prevIndex]){
                changeIndex = nextIndex;
                break;
            }
        }

        if(changeIndex == -1)
            return false;

        for(int i = n-1; i > changeIndex; i--){
            if(numbers[i] > numbers[changeIndex]){
                swap(numbers, i, changeIndex);
                break;
            }
        }
        while(++changeIndex < --n){
            swap(numbers,changeIndex,n);
        }
        return true;
    }

    //배열의 순서변경
    private void swap(int[] numbers, int a, int b){
        int temp = numbers[a];
        numbers[a] = numbers[b];
        numbers[b] = temp;
    }
}

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)