[Java] 프로그래머스 피로도

1. 문제 분석

 

피로도에 따라 던전을 최대 몇개까지 들어갈 수 있는지를 구하는 문제다.

요구피로도와 사용피로도가 있어 현재 피로도가 요구피로도보다 낮다면 던전에 들어가지 못한다.

 

처음 접근은 던전 배열을 정렬해서 들어가야하나 싶지만 이러면 전혀 답을 구할 수 없다.

값도 작으니 나는 완전탐색을 통해서 문제를 해결했다.

 

2022.09.21 - [문법/Java] - [Java] 순열

[Java] 순열

던전의 개수만큼 크기를 가진 1차원 배열을 생성한다. 그리고 그 배열에 0부터 순차적으로 값을 입력해준다.

그리고 순열을 돌리면 된다. 뽑고자 하는수는 던전의 개수만큼 뽑아야 모든 던전을 검사할 수 있다.

 

테스트케이스의 예시를 보자.

현재 피로도는 80이고 각 던전은 (요구: 80, 사용: 20), (요구: 50, 사용: 40), (요구: 30, 사용: 10)이다.

 

순열을 사용해 어떤순서로 돌지 생각해보자.

1을 처음으로 시작한다면 1 -> 2 -> 3, 1 -> 3 -> 2가 존재한다.

2를 처음으로 시작한다면 2 -> 1 -> 3, 2 -> 3 -> 1이 존재한다.

3을 처음으로 시작한다면 3 -> 1 -> 2, 3 -> 2 -> 1이 존재한다.

 

위의 순서로 가능한 던전의 개수의 최대값을 출력하면 끝이다. 순열만 생각하면 편하게 풀었다.

2. 구현

import java.io.IOException;


public class Solution {
    int answer;

    public static void main(String[] args) throws IOException {
        Solution solution = new Solution();
        int k = 50;
        int[][] arr = {
                {80, 20},
                {50, 40},
                {30, 10}
        };
        System.out.println(solution.solution(k, arr));


    }

    public int solution(int k, int[][] dungeons) {
        //2차원 배열 {요구 필요도, 사용 피로도};

        //순열로 던전을 도는 경우를 구함
        //던전을 최대한 많이 돌 수 있는 경우를 출력
        int size = dungeons.length;

        int[] arr = new int[size];
        int[] output = new int[size];
        boolean[] visited = new boolean[size];

        for (int i = 0; i < size; i++) {
            arr[i] = i;
        }

        perm(arr, output, visited, 0, size, size, k, dungeons);

        return answer;
    }

    public void calc(int[] arr, int k, int[][] dungeons) {
        //계산, arr 은 구한 순열, k는 피로도, dungeons는 던전
        int result = 0;
        for(int i = 0; i<arr.length; i++){
            if(dungeons[arr[i]][0] <= k){
                //던전 입장 가능
                k -= dungeons[arr[i]][1];
                result++;
            }
        }
        answer = Math.max(result, answer);
    }

    public void perm(int[] arr, int[] output, boolean[] visited, int depth, int n, int r, int k, int[][] dungeons) {
        if (depth == r) {
            int[] tempArr = new int[n];
            for (int i = 0; i < r; i++) {
                tempArr[i] = output[i];
            }
            calc(tempArr, k, dungeons);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                output[depth] = arr[i];
                perm(arr, output, visited, depth + 1, n, r, k, dungeons);
                output[depth] = 0;
                visited[i] = false;
            }
        }
    }
}

전체적인 구조는 순열로 던전 이동 방향 정하기 -> 던전을 몇개 돌 수 있는지 확인이다.

처음엔 tempArr를 class의 멤버변수로 선언했는데 값이 꼬여서 메소드 내부에 선언했다.

3. 마무리

지금 싸피에서 푸는 알고리즘은 감도 안잡혀서 기초부터 한다는 생각으로 푸는데 나름 실력이 늘은 기분이 든다.

예전같으면 이런문제 풀지도 못했을텐데 ㅎㅎ..