636. Exclusive Time of Functions (Array, Stack)

링크 - https://leetcode.com/problems/exclusive-time-of-functions/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

우리는 스택을 사용해서 이 문제를 풀 수 있다. 한번에 하나의 함수만 실행이 되므로, end가 왔을때 pop을 하면 id체크를 하지 않아도 된다는 보장이 있다.

1. 먼저 정답을 [0] * n으로 초기화 한다.

2. logs를 for문으로 돌면서 처리를 시작한다.

2.1 만약 type이 start면, stack을 확인하고 만약 존재하면 정답에 현재 시간 - stack의 start timestamp만큼 더한다. 그리고 stack에 (fid, ftime) tuple형식으로 집어넣는다.

2.2 만약 type이 end면, stack을 pop해서 정답에 현재시간 - stack의 start timestamp + 1만큼 더한다. 그리고 stack이 존재하면 peek의 timestamp를 timestamp + 1로 설정한다.

3. 정답을 반환한다.

Code

class Solution:
    def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
        stack = []
        ans = [0] * n

        for log in logs:
            fid, ftype, ftime = log.split(":")
            fid = int(fid)
            ftime = int(ftime)
            if ftype == "start":
                if stack:
                    ans[stack[-1][0]] += (ftime - stack[-1][1])
                stack.append((fid, ftime))
            else:
                end_fid, end_ftime = stack.pop()
                ans[end_fid] += (ftime - end_ftime + 1)
                if stack:
                    prev_fid, prev_ftime = stack.pop()
                    stack.append((prev_fid, ftime + 1))

        return ans

Complexity

Time Complexity: O(n)

Space Complexity: O(n) stack에는 최대 n/2개의 아이템이 들어있을 수 있다.