프로그래머스 2) 피로도

피로도

자주 나오는 유형의 문제. 방문 기록을 관리하면서 조건별로 totalCount를 증가시켜주면 되는 간단한 문제.

python에서 java로 바꾼지 얼마 안되어서 stack이나 deque 사용에 익숙하지 않고, 배열 또한 python은 여러 자료구조를 한꺼번에 넣을수 있지만 java는 그게 어렵기 때문에 object[]로 넣어서 꺼내쓸때 다시 자료형을 변환시켜주어서 해결했다.

import java.util.*;

class Solution {
    
    public int dfs(int tired,int num,int[][] dungeons,boolean[] visited,int totalCount){
        int maxValue = 0;
        Deque<Object[]> deque = new ArrayDeque<>();
        
        boolean[] newArray = visited.clone();
        
        if (tired >= dungeons[num][0]){
            newArray[num] = true;    
            deque.addFirst(new Object[]{tired - dungeons[num][1],newArray,totalCount+1});
        }
        
        while(!deque.isEmpty()){
            Object[] pop = deque.removeLast();
            
            int now =(int) pop[0];
            boolean[] cloneNewArray =(boolean[]) pop[1];
            int popTotalCount =(int) pop[2];
            
            for(int i=0; i<cloneNewArray.length; i++){
                if(!cloneNewArray[i] && now >= dungeons[i][0]){
                    boolean[] popNewArray = cloneNewArray.clone();
                    popNewArray[i] = true;
                    deque.addFirst(new Object[]{now - dungeons[i][1],popNewArray,popTotalCount + 1});
                }else{
                    maxValue = Math.max(maxValue,popTotalCount);
                }
            }
        }
        
        return maxValue;
    }
    
    public int solution(int k, int[][] dungeons) {
        int answer = 0;
        boolean[] visited = new boolean[dungeons.length];
        Arrays.fill(visited,false);
        
        for(int i=0;i<dungeons.length; i++){
            answer = Math.max(dfs(k,i,dungeons,visited,0),answer);
        }
        return answer;
    }
    
}