C++의 배타적 함수 시간

단일 스레드 CPU에서 일부 기능을 실행한다고 가정합니다. 이제 각 함수는 0과 N-1 사이의 고유 ID를 갖습니다. 함수가 시작되거나 종료될 때를 설명하는 타임스탬프 순서로 로그를 저장합니다.

여기서 각 로그는 "{function_id}:{"start" | "end"}:{timestamp}" 형식으로 작성된 문자열입니다. 예를 들어, 문자열이 "0:start:3"과 같다면 이것은 id 0의 함수가 타임스탬프 3의 시작 부분에서 시작되었음을 의미합니다. "1:end:2"는 id 1의 함수가 타임스탬프의 끝에서 종료되었음을 의미합니다. 2. 함수의 배타적 시간은 이 함수에 소요된 시간의 단위 수입니다.

따라서 입력이 n =2이고 로그 =["0:start:0","1:start:2","1:end:5","0:end:6"]인 경우 출력은 다음과 같습니다. [3,4]가 됩니다. 이는 함수 0이 시간 0의 시작 부분에서 시작한 다음 시간 2 단위를 실행하고 시간 1의 끝에 도달하기 때문입니다. 그 후 함수 1은 시간 2의 시작 부분에서 시작하여 시간 단위 4개를 실행하고 시간 5에 종료됩니다. 함수 0은 시간 6의 시작 부분에서 다시 실행되고 시간 6의 끝에서도 종료되므로 1단위 시간 동안 실행됩니다. 따라서 함수 0은 2 + 1 =3 단위의 총 실행 시간을 사용하고 기능 1은 총 4 단위의 실행 시간을 사용함을 알 수 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 크기가 n인 배열 ret를 정의하고 스택 st를 정의합니다.

• j :=0, 이전 :=0

• 범위 0에서 로그 배열의 크기 – 1까지의 i에 대해

  • temp :=logs[i], j :=0, id :=0, num :=0, type :=빈 문자열

• 반면 temp[j]는 콜론이 아닙니다.

  • id :=id * 10 + temp[j]를 숫자로

  • j를 1 증가

• j를 1 증가

• 반면 temp[j]는 콜론이 아닙니다.

  • 유형 :=유형 연결 temp[j]

  • j를 1 증가

• j를 1 증가

• 동안 j <온도의 크기

  • num :=num * 10 + temp[j]를 숫자로

  • j를 1 증가

• 유형 =시작인 경우

  • st가 비어 있지 않은 경우

    • ret[stack top element]를 num만큼 증가 – 이전

  • st에 d 삽입, 이전 :=num

• 그렇지 않으면

  • x :=st의 상단, 스택의 상단 삭제

  • ret[x] :=ret[x] + (숫자 + 1) – 이전

  • 이전 :=숫자 + 1

• 리턴 렛

예시(C++)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> exclusiveTime(int n, vector<string>& logs) {
      vector <int> ret(n);
      stack <int> st;
      int id, num;
      int j = 0;
      string temp;
      string type;
      int prev = 0;
      for(int i = 0; i < logs.size(); i++){
         temp = logs[i];
         j = 0;
         id = 0;
         num = 0;
         type = "";
         while(temp[j] != ':'){
            id = id * 10 + (temp[j] - '0');
            j++;
         }
         j++;
         while(temp[j] != ':'){
            type += temp[j];
            j++;
         }
         j++;
         while(j < temp.size()){
            num = num * 10 + temp[j] - '0';
            j++;
         }
         if(type == "start"){
            if(!st.empty()){
               ret[st.top()] += num - prev;
            }
            st.push(id);
            prev = num;
         } else {
            int x = st.top();
            st.pop();
            ret[x] += (num + 1) - prev;
            prev = num + 1;
         }
      }
      return ret;
   }
};
main(){
   vector<string> v = {"0:start:0","1:start:2","1:end:5","0:end:6"};
   Solution ob;
   print_vector(ob.exclusiveTime(2, v));
}

입력

2
["0:start:0","1:start:2","1:end:5","0:end:6"]

출력

[3, 4, ]