피로도(Lv.2)

 

---

 

문제 설명

 

 

 

입출력 예시

 

 

요약

던전을 최대로 많이 돌 수 있는 경우의 수 구하기

 

---

 

풀이

 

접근 방식

1. 완전탐색을 위한 모든 경우의 수 구하기

  → 던전의 개수가 3개인 경우: 012, 021, 102, 120, 201, 210  

 

---

 

코드리뷰

import java.util.*;

class Solution {
    HashSet<String> set = new HashSet<>();
    // 모든 경우의 수를 구하는 재귀함수
    public void recursive(String comb, String remains, int maxLength) {
        if(!comb.isBlank() && comb.length() == maxLength) {
            set.add(comb);
        }
        for(int i = 0; i < remains.length(); i++) {
            recursive(comb + remains.substring(i, i+1),	// remains의 첫 번째 문자 떼서 다음 재귀함수의 첫 번째 인자로 넘김
                      remains.substring(0, i) + remains.substring(i+1),	// 해당 문자를 제외한 나머지 문자열을 두 번째 인자로 넘김
                      maxLength);	// 던전의 개수를 문자열의 maxLength로 전달
        }
    }
    
    public int solution(int k, int[][] dungeons) {
        List<Integer> answerList = new ArrayList<>();
        String substr = "";
        
        for(int i = 0; i < dungeons.length; i++) {
            substr += String.valueOf(i);	// 'length = 던전의 개수'인 숫자 문자열 생성
        }
        
        recursive("", substr, substr.length());	// 경우의 수 구하는 재귀함수 호출
        
        for(String val : set) {
            int tired = k;	// 피로도
            int count = 0;	// 던전 카운트
            for(int i = 0; i < val.length(); i++) {	// 각 경우의 수를 전부 탐색
                if(tired >= dungeons[Integer.valueOf(val.substring(i, i+1))][0]) {	// 피로도가 최소 피로도 이상이면
                    tired -= dungeons[Integer.valueOf(val.substring(i, i+1))][1];	// 던전 돌고 피로도 감소
                    count++;	// 던전 카운트 증가
                } else {	// 피로도가 최소 피로도 미만이면
                    break;	// 해당 경우의 수 탈출
                }
            }
            answerList.add(count);	// 던전을 돌 수 있을만큼 돌고 난 후 던전 카운트를 list에 add
        }
        int answer = Collections.max(answerList);	// 던전 카운트 중 최댓값 구하기
        return answer;
    }
}