LV2 피로도 (Java)

 

---

 

문제

 

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

프로그래머스

 

풀이

 

문제에서 주어지는 dungeons 의 최대 크기가 8인 것을 보고 완탐을 해도 되겠구나 라고 판단할 수 있었다.

 

해당 문제는 순열을 만들어서, 그 순서대로 방문을 해보고 가장 큰 값이 무엇인지 판단해주면 된다.

 

dungeons의 크기가 3일 경우 순열을 구하면

 

0 1 2

0 2 1

1 0 2

1 2 0

2 0 1

2 1 0

 

과 같이 6개 값이 나오는데, 모두 시도해보면서 가장 많이 방문할 수 있는 경우를 체크해주면 된다.

 

따라서 순열만 만들 수 있다면 바로 풀 수 있는 문제이다. 

 

코드

import java.util.*;

class Solution {
    
    public List<ArrayList<Integer>> ways = new ArrayList<>();
    
    /*
    @cnt: 내가 뽑은 값의 개수
    @ l : 뽑아야할 limit 
    @visited : 방문한 요소 체크
    @arr : 내가 뽑아둔 배열
    */
    public void permutation(int cnt, int l, boolean[] visited, ArrayList<Integer> arr){
        if(cnt >= l){
            ways.add(new ArrayList<Integer>(arr));
            return;
        }
        
        for(int i=0; i<l; i++){
            if(!visited[i]){
                arr.add(i);
                visited[i] = true;
                permutation(cnt+1, l, visited, arr);
                arr.remove(new Integer(i));
                visited[i] = false;
            }
        }
    }
                            
    
    public int solution(int k, int[][] dungeons) {
        int answer = -1;
        int l = dungeons.length;
        boolean visited[] = new boolean[l];

        permutation(0, l, visited, new ArrayList<Integer>());
        
        for(int i=0; i<ways.size(); i++){
            int have = k;
            int temp = 0;
            
            for(Integer target : ways.get(i)){
               if(have >= dungeons[target][0]){
                    have -= dungeons[target][1];
                    temp++;
                } 
            }
            answer = Math.max(answer, temp);
        }
        return answer;
    }
}

 

후기

- 순열값들을 모두 저장한다음 한번에 비교하려고 클래스 변수 ways 를 사용했다. 단, 순열값을 넣어줄때 arr이 객체기 때문에 깊은 복사로 넣어주어야 함수를 벗어나도 유지되었다.

 

- List.remove 메소드를 이용했다. 근데 remove는 오버로딩이 되어있는데 int값과 object 값을 넣을 수 있다. 처음엔 int 값을 넣고 해당 값을 없애고 싶었으나, index로 인식이 되었다. 이후에 Integer로 바꾸었더니 원하는 값이 삭제되었다.

 

문제자체는 쉬웠으나, 파이썬은 itertools 로 순열 및 조합을 쉽게 구할 수 있으나 자바는 구현해야 해서 좀 헷갈렸다. 순열과 조합의 개념과, 코드 작성에 도움을 받았던 링크를 첨부하겠다.

 

https://recipesds.tistory.com/entry/%EC%B4%88%EA%B0%84%EB%8B%A8-Permuation%EC%88%9C%EC%97%B4%EA%B3%BC-Combination%EC%A1%B0%ED%95%A9

초간단 Permuation(순열)과 Combination(조합)

 

https://bcp0109.tistory.com/14

순열 Permutation (Java)