★Minimum Difficulty of a Job Schedule★

작성을 마치신 후 상태를 변경해 주세요!

LeetCode - The World's Leading Online Programming Learning Platform

★다시 풀어볼 고난이도 문제★ (1시간동안 고민 후 못풀었음)

문제 파악 [필수 작성]

문제이해

1차

i번째 작업하려면 그 이전작업 다 끝내야가능
하루에 한개 이상 해야됨
매일 최대 난이도를 합한게 총 난이도
하루 난이도는 그날의 최대난이도
만약 매일 작업 진행 불가시 -1 리턴
작업 최소량을 찾아야함

2차

문제를 잘못이해함.
무조건 jobDifficulty 에 주어진 순서대로 일을 처리해야함
앞에서부터 몇개 끊을건지 생각해야함

제한 조건 확인

job 갯수 300개
난이도 0~1000
d 1~10
중복값 가능

아이디어

1차

그냥 내림차순으로 쫙 정렬한다음에
d갯수만큼 뒤에서부터 끊으면 되는거아닌가?
뭐이리 쉽지? 문제를 잘못이해한건가..

2차

만약 d가 jobDifficulty 길이보다 길면 -1 리턴
d가 1이면 max 값을 리턴
똑같으면, 그냥 리스트의 합을 리턴
더 작으면, d=1 일때부터 바깥놈들중
작은애들부터 뜯을수 있는만큼 뜯어나가야됌
양쪽이 빠질수있는 구멍이 많을수록 유리한 구조

d=1 일때부터 deque에 넣고 양쪽 중 작은 놈을 뽑고,
뽑은방향에서 뽑은놈보다 작은놈이면 더 큰놈나올때까지 계속 뽑기

예제
5 8 9 4 6 2, d=4
10 8 9 2 7 3 4, d=4
4 10 8 9 2 7 3 4, d=?
4 3 10 8 9 2 4

시간복잡도

2차

jobDifficulty 가 300밖에 안된다는건
반복문 맘껏 쓰라는 이야기로 보임 -> 완탐?

완탐시 -> 300 C 10 300 = 300 ^ 11 / 10...*1 -> 절대 안됨

(2 + 4 + . . . + 20) 300? = 220 300?

자료구조

접근 방법 [필수 작성]

자유 형식

코드 구현 [필수 작성]

1차

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        rs_jobDifficulty = list(reversed(sorted(jobDifficulty)))
        result = 0
        if d > len(rs_jobDifficulty):
            return -1
        else:
            r_p = -1
            while r_p > -d:
                result += rs_jobDifficulty[r_p]
                r_p -= 1
            result += rs_jobDifficulty[0]
            return result

2차

from collections import deque
from collections import defaultdict

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        q_num = 1
        q_dict = defaultdict(deque)
        if d > len(jobDifficulty):
            return -1
        elif d == 1:
            return max(jobDifficulty)
        elif d == len(jobDifficulty):
            return sum(jobDifficulty)
        else:
            q_dict[1] = deque([jobDifficulty])
            while q_num < d:
                q_num += 1
                min_val = 1001
                for k,q in q_dict.items():
                    q[0] q[-1]
                q_dict[q_num] = 
            print(q_dict)
            # while q_num < d:
            #     if q[0] < q[-1]
            return 0 
        # 더 작으면, d=1 일때부터 바깥놈들중
        # 작은애들부터 뜯을수 있는만큼 뜯어나가야됌
        # 양쪽이 빠질수있는 구멍이 많을수록 유리한 구조

        # d=1 일때부터 deque에 넣고 양쪽 중 작은 놈을 뽑고,
        # (양쪽이 같으면 뽑을만큼 뽑았을때 반대끝이 더 작아지는 놈 )
        # 뽑은방향에서 뽑은놈보다 작은놈이면 더 큰놈나올때까지 계속 뽑기
        # -> incremental 하게 탐색을 진행해야하는데 구현이 겁나 어려움
        # -> 이렇게까지 어렵게 구현하는 문제는 아닐것같아서 디벨롭 포기
        

3차

해설 코드 이해안가서 유튜브 보고 O(n^2 * d) 로 하는 dfs 방법 공부

https://www.youtube.com/watch?v=DAAULrZFeLI

스터디에서 해설코드 같이 연구해보기

from collections import deque
from collections import defaultdict

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        if d > len(jobDifficulty):
            return -1
        elif d == 1:
            return max(jobDifficulty)
        elif d == len(jobDifficulty):
            return sum(jobDifficulty)
        else:
            cache = {}
            def dfs(i,d,cur_max):
                if i == len(jobDifficulty):
                    return 0 if d == 0 else float("inf")
                if d == 0:
                    return float("inf")
                if (i,d,cur_max) in cache:
                    return cache[(i,d,cur_max)]
                cur_max = max(cur_max,jobDifficulty[i])
                result = min(dfs(i+1,d,cur_max),cur_max + dfs(i+1,d-1,-1))
                cache[(i,d,cur_max)] = result

                return result
                
            return dfs(0,d,-1)

배우게 된 점 [필수 작성]

해설코드 점화식 만드는법 및 DP 테이블 아이디어 이해해보기

코드는 나중에 이해

질문 [ 필수 X ]

댓글로 또는 이곳에 질문 남겨주세요.