[Mock] Google 9

551. Student Attendance Record I

You are given a string s representing an attendance record for a student where each character signifies whether the student was absent, late, or present on that day. The record only contains the following three characters:

• 'A': Absent.
• 'L': Late.
• 'P': Present.

The student is eligible for an attendance award if they meet both of the following criteria:

• The student was absent ('A') for strictly fewer than 2 days total.
• The student was never late ('L') for 3 or more consecutive days.

Return true if the student is eligible for an attendance award, or false otherwise.

My Answer 1: Accepted (Runtime: 24 ms - 94.63% / Memory Usage: 14.2 MB - 43.38%)

class Solution:
    def checkRecord(self, s: str) -> bool:
        absent = 0
        late = 0
        
        for i in range(len(s)):
            if s[i] == "A":
                absent += 1
                late = 0
            elif s[i] == "L":
                late += 1
            else:
                late = 0
            
            if absent > 1 or late > 2:
                return False
        
        return True

연속되는 Late 와 비연속되는 Absent 를 계산해서 각각 3, 2 이상이면 False

---

743. Network Delay Time

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

My Answer 1: Wrong Answer (9 / 52 test cases passed.)

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        dic = {}
        nums = [0]*(n+1)
        
        for i in range(len(times)):
            if times[i][0] not in dic:
                dic[times[i][0]] = [[times[i][1],times[i][2]]]
            else:
                dic[times[i][0]].append([times[i][1],times[i][2]])
        
        if k not in dic:
            return -1
        
        def func(dic, idx, s):
            if idx not in dic or nums[idx]:
                nums[idx] = s
                return s
            
            ans = s
            arr = dic[idx]
            for i in range(len(arr)):
                if nums[arr[i][0]]:
                    nums[arr[i][0]] = min(nums[arr[i][0]], s+arr[i][1])
                    return
                else:
                    nums[arr[i][0]] = s+arr[i][1]
                    
                func(dic, arr[i][0], s+arr[i][1])
        
        func(dic, k, 0)
        
        return max(nums)

보자마자 거지 같았던 기억이 떠올랐네요^^

일단 dic 에 각 노드마다 [연결된 노드, weight] 를 쭉 구해주고
시작값인 k 와 연결된 노드가 없으면 -1 return

재귀 써서 nums 리스트에 각 노드들까지 도착하는데 걸린 weight 누적값을 넣어주기

방문했던 전적이 있는 노드는 최소 weight 값으로 update
마지막엔 weight 가 가장 높은 max(nums) return

근데 잘 안됐네요...^^

Solution 1: Accepted (Runtime: 900 ms - 12.51% / Memory Usage: 17.8 MB - 5.86%)

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        graph = collections.defaultdict(list)
        for u, v, w in times:
            graph[u].append((w, v))

        dist = {node: float('inf') for node in range(1, n+1)}

        def dfs(node, elapsed):
            if elapsed >= dist[node]: return
            dist[node] = elapsed
            for time, nei in sorted(graph[node]):
                dfs(nei, elapsed + time)

        dfs(k, 0)
        ans = max(dist.values())
        return ans if ans < float('inf') else -1

풀었던거랑 유사한 루션이..

graph 딕셔너리 만들어서 연결되는 지점이랑 시간을 묶어서 넣어줌

dist 라는 딕셔너리? 도 사용 -> {1: inf, 2: inf} 이런식으로 저장된다 (n 의 길이)

dfs 함수로 재귀 돌면서 elapsed 에는 총 시간을 누적으로 저장

if elapsed >= dist[node]: return 이거는 최솟값을 갖기 위해서 해주는 듯