32일차)알고리즘 문제(피로도), 챌린지반 강의 1회차, 추가 과제

>알고리즘 문제

1. 피로도

1)문제

문제 설명

XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던전 탐험을 마쳤을 때 소모되는 "소모 피로도"가 있습니다. "최소 필요 피로도"는 해당 던전을 탐험하기 위해 가지고 있어야 하는 최소한의 피로도를 나타내며, "소모 피로도"는 던전을 탐험한 후 소모되는 피로도를 나타냅니다. 예를 들어 "최소 필요 피로도"가 80, "소모 피로도"가 20인 던전을 탐험하기 위해서는 유저의 현재 남은 피로도는 80 이상 이어야 하며, 던전을 탐험한 후에는 피로도 20이 소모됩니다.

이 게임에는 하루에 한 번씩 탐험할 수 있는 던전이 여러개 있는데, 한 유저가 오늘 이 던전들을 최대한 많이 탐험하려 합니다. 유저의 현재 피로도 k와 각 던전별 "최소 필요 피로도", "소모 피로도"가 담긴 2차원 배열 dungeons 가 매개변수로 주어질 때, 유저가 탐험할수 있는 최대 던전 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• k는 1 이상 5,000 이하인 자연수입니다.
• dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.
  • dungeons의 가로(열) 길이는 2 입니다.
  • dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다.
  • "최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다.
  • "최소 필요 피로도"와 "소모 피로도"는 1 이상 1,000 이하인 자연수입니다.
  • 서로 다른 던전의 ["최소 필요 피로도", "소모 피로도"]가 서로 같을 수 있습니다.

2)솔루션

class Solution {
    fun solution(k: Int, dungeons: Array<IntArray>): Int {
        var answer: Int = 0
        var st=k
        val sets=hashSetOf<IntArray>()
        for(i in dungeons) sets.add(i)
        return fac(sets,st,0)
    }
    
    fun fac(sets:HashSet<IntArray>,st:Int,total:Int):Int{
        val answers=ArrayList<Int>()
        for(i in sets){
            if(i[0]<=st){
                val tmpset=HashSet(sets)
                tmpset.remove(i)
                answers+=fac(tmpset,st-i[1],total+1)
            }
        }
        
        return answers.maxOrNull() ?: total
    }
}

-최대길이가 8밖에 안되니 모든 방문순서에 대한 재귀함수를 이용해 전수조사로 답을 구함

-단, 던전방문 중간에 피로도 부족으로 진행이 불가능해 지는 구간이 존재할 수 있으므로 조건문을 붙여 체크

-던전 방문은 남은 던전 집합에서 하나를 골라 방문하고 제거하는 방식으로 구현했음

 

 

 

>챌린지반 강의 정리

 

1.다형성-이 타입도 될 수 있고 저 타입도 될 수 있는 성질
ex)number는 int가 될수도 long이 될 수도 있음
2.인터페이스로 특정 클래스 객체만 골라내기 가능
ex)interface하나 선언해서 골라내고자 하는 객체에만 인터페이스를 상속시켜준뒤 is interface로 골라냄 
3. abstract클래스에서도 멤버에 open과 abstract과 키워드 없는 것 세가지중 하나로 선택가능
-없는것: 그냥 상속받아서 쓰는것으로 오버라이드 안함
-open: 함수본문이 적혀있는 것으로 오버라이드 여부는 자유 =>super.fun(매개변수)를 쓰면 기존 함수의 내용이 실행됨. 위치는 본문 어디든 상관X
-abstract: 함수본문이 없는것. 반드시 오버라이드 해야함
4. 캡슐화: 접근제한자로 접근을 막는것 
ex)외부에서 접근 못하게 하려면 private: 내부 함수를 통해서는 접근가능

 

 

>추가 과제

https://appdevelopjava.tistory.com/42