[Mock] Random 2

---

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.38% / Memory Usage: 14.1 MB - 72.11%)

class Solution:
    def checkRecord(self, s: str) -> bool:
        late = 0
        absent = 0
        
        for i in range(len(s)):
            if s[i] == "L":
                late += 1
            else:
                if late:
                    late = 0
                if s[i] == "A":
                    absent += 1
                    
            if late >= 3 or absent >= 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 (7 / 52 test cases passed.)

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        dic = {}
        
        tmp = 0
        circle = 0
        
        for i in range(len(times)):
            dic[i+1] = []
            if times[i][0] == k:
                circle = times[i][1]
                tmp = times[i][2]
        
        for i in range(len(times)):
            dic[times[i][0]].append([times[i][1],times[i][2]])
        
        if k == n:
            for i in range(len(times)):
                if times[i][0] == circle and times[i][1] == n:
                    return max(tmp, times[i][2])
        
        self.result = float('inf')
        
        def func(dic, k, n, r):
            if r != 0 and k == n:
                self.result = min(self.result, r)
                return
            
            if k not in dic:
                self.result = float('inf')
                return
            
            for i in range(len(dic[k])):
                func(dic, dic[k][i][0], n, r+dic[k][i][1])
        
        func(dic, k, n, 0)
        
        if self.result == float('inf'):
            return -1
        
        return self.result

dic 이용해서 값으로 [연결되는 지점, time] 을 저장
circle 이 만들어질 땐 time 의 계산이 달라지므로 따로 설정함..
나머지는 n 이 나올 때까지 재귀 돌리기 -> time 을 누적해서 더해줌

문제 이해를 잘못한 거 같기도 하고...
그래프에 많이 약한 듯...ㅠ

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 이거는 최솟값을 갖기 위해서 해주는 듯

Dijkstra's Algorithm

Solution 2: Accepted (Runtime: 488 ms - 41.29% / Memory Usage: 16.2 MB - 49.73%)

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        q, t, adj = [(0, k)], {}, collections.defaultdict(list)
        for u, v, w in times:
            adj[u].append((v, w))
        while q:
            time, node = heapq.heappop(q)
            if node not in t:
                t[node] = time
                for v, w in adj[node]:
                    heapq.heappush(q, (time + w, v))
        return max(t.values()) if len(t) == n else -1

첫번째랑 비슷한데... queue 이용

adj 에는 똑같이 (v, w) 를 넣어줌

q 에는 시작값으로 (0, k) 를 주고 pop 해가면서 t 에 시간값을 저장

time 은 누적이 된다.

---

n 이 노드의 개수였군

k 부터 시작해서 n 개의 모든 노드에 시그널 보내나봐..