[Mock] Random 21

두번째 문제는 시간 끝나자마자 풀었음...^^

---

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Given an array of integers nums and an integer limit, return the size of the longest non-empty subarray such that the absolute difference between any two elements of this subarray is less than or equal to limit.

My Answer 1: Time Limit Exceeded (55 / 61 test cases passed.)

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        
        self.ans = 1
        for i in range(len(nums)):
            a = i
            b = i
            mi = nums[i]
            ma = nums[i]
            for j in range(i+1, len(nums)):
                if ma < nums[j]:
                    ma = nums[j]
                    a = j
                elif mi > nums[j]:
                    mi = nums[j]
                    b = j
                if abs(nums[a]-nums[b]) <= limit:
                    m = a if a < b else b
                    self.ans = max(self.ans, abs(j-i)+1)
            
        
        return self.ans

최댓값 a 와 최솟값 b 를 갱신해가면서 subarray 의 최대 길이 구하기...

Solution 1: Accepted (Runtime: 700 ms - 61.58% / Memory Usage: 24.1 MB - 65.26%)

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        min_deque, max_deque = deque(), deque()
        l = r = 0
        ans = 0
        while r < len(nums):
            while min_deque and nums[r] <= nums[min_deque[-1]]:
                min_deque.pop()
            while max_deque and nums[r] >= nums[max_deque[-1]]:
                max_deque.pop()
            min_deque.append(r)
            max_deque.append(r)
            
            while nums[max_deque[0]] - nums[min_deque[0]] > limit:
                l += 1
                if l > min_deque[0]:
                    min_deque.popleft()
                if l > max_deque[0]:
                    max_deque.popleft()
            
            ans = max(ans, r - l + 1)
            r += 1
                
        return ans

deque 2 개 사용

r 이 subarray 의 시작값이 되는듯..? ex) [8,2,4,7] => 8 로 시작하는 sub~, 2 로 ~...

min_deque[0] 는 지금 보고 있는 window 의 최솟값, min_deque[0] 는 최댓값

nums[max_deque[0]] - nums[min_deque[0]] 가 limit 을 벗어나면 popleft

ex) [8,2,4,7] => 8, 4 는 안되는 것처럼 연속되는 subarray 만 가능한 점이 포인트인듯

어렵다...ㅠ

참고 1: https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/discuss/609771/JavaC%2B%2BPython-Deques-O(N)
참고 2: https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/discuss/609708/Python-Clean-Monotonic-Queue-solution-with-detail-explanation-O(N)

풀이 방식이 전에 풀었던 239. Sliding Window Maximum 문제와 유사한듯
https://leetcode.com/problems/sliding-window-maximum/

---

1376. Time Needed to Inform All Employees

A company has n employees with a unique ID for each employee from 0 to n - 1. The head of the company is the one with headID.

Each employee has one direct manager given in the manager array where manager[i] is the direct manager of the i-th employee, manager[headID] = -1. Also, it is guaranteed that the subordination relationships have a tree structure.

The head of the company wants to inform all the company employees of an urgent piece of news. He will inform his direct subordinates, and they will inform their subordinates, and so on until all employees know about the urgent news.

The i-th employee needs informTime[i] minutes to inform all of his direct subordinates (i.e., After informTime[i] minutes, all his direct subordinates can start spreading the news).

Return the number of minutes needed to inform all the employees about the urgent news.

My Answer 1: Accepted (Runtime: 1400 ms - 46.18% / Memory Usage: 52.9 MB - 23.22%)

class Solution:
    def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
        ans = 0
        dic = {headID:[]}
        
        for i in range(len(manager)):
            if manager[i] == -1:
                continue
            elif manager[i] not in dic:
                dic[manager[i]] = [i]
            else:
                dic[manager[i]].append(i)
        
        def func(ID):
            if ID not in dic:
                return 0
            
            tmp = 0
            for i in dic[ID]:
                tmp = max(tmp, func(i))
            return informTime[ID] + tmp
        
        ans = func(headID)
        
        return ans

시간 종료되자마자 풀린 경우는 뭥미...

dic 에 manager 마다 맡은 id 들을 저장

headID 부터 재귀 돌려서 informTime[ID] 들을 저장해줌

tmp = max(tmp, func(i)) => 가장 오래 걸린 manager 라인 값을 더해주기

원래는 max 값 말고 그냥 더했는데 이거 하나 고치니까 됐다...^^

ex) 1 -> 2 -> 3 & 1 -> 4 -> 5 처럼 1 부터 연결된 라인이 여러개라면
1 다음 2, 4 는 informTime 이 큰 값만큼 기다렸다가 3, 5 봐야되는줄...