문제 개요
단일 스레드(single-threaded) CPU에서 여러 함수를 실행한다고 가정해 보겠습니다. 각 함수는 0부터 N-1 사이의 고유한 ID를 가지며, 함수가 호출되거나 종료되는 시점을 나타내는 로그가 타임스탬프 순서대로 저장됩니다.
각 로그는 다음과 같은 형식의 문자열입니다: "{function_id}:{"start" | "end"}:{timestamp}". 예를 들어 "0:start:3"은 ID가 0인 함수가 타임스탬프 3의 시작 시점에 실행을 시작했다는 뜻이고, "1:end:2"는 ID가 1인 함수가 타임스탬프 2의 마지막 시점에 종료되었다는 뜻입니다. 여기서 말하는 배타적 시간(exclusive time)은 해당 함수가 실제로 실행에 소비한 시간 단위의 총합을 의미합니다.
예제로 이해하기
n = 2이고 logs = ["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가 됩니다.
접근 방법: 스택 활용
함수 호출은 중첩될 수 있으므로, 스택(stack)을 사용하면 현재 실행 중인 함수를 손쉽게 추적할 수 있습니다. 알고리즘은 다음과 같이 진행됩니다.
- 크기가 n인 배열 ret와 정수형 스택 st를 선언합니다.
- j := 0, prev := 0으로 초기화합니다.
- i를 0부터 로그 배열 크기 - 1까지 반복합니다.
- temp := logs[i], j := 0, id := 0, num := 0, type := 빈 문자열로 초기화합니다.
- temp[j]가 콜론(:)이 아닌 동안 id := id * 10 + temp[j]의 숫자 값을 계산하며 j를 증가시켜 함수 ID를 파싱합니다.
- j를 1 증가시킨 뒤, temp[j]가 콜론이 아닌 동안 type에 temp[j]를 이어 붙여 "start" 또는 "end"를 추출합니다.
- j를 1 증가시킨 뒤, j가 temp의 길이보다 작은 동안 num := num * 10 + temp[j]의 숫자 값을 계산해 타임스탬프를 파싱합니다.
- type이 "start"라면:
- 스택이 비어 있지 않으면 ret[스택 최상단 원소]에 (num - prev)를 더합니다. 즉, 지금까지 경과한 시간을 이전 함수의 배타적 시간에 누적합니다.
- 현재 함수 ID를 스택에 push하고 prev := num으로 갱신합니다.
- type이 "end"라면:
- x := 스택 최상단 값을 pop합니다.
- ret[x]에 ((num + 1) - prev)를 더합니다. 종료 타임스탬프도 포함해 계산하는 것이 핵심입니다.
- prev := num + 1로 갱신합니다.
- 모든 로그를 처리한 후 ret를 반환합니다.
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]
핵심 정리
이 문제의 핵심은 두 가지입니다. 첫째, 함수 호출이 중첩될 수 있으므로 스택으로 실행 흐름을 관리해야 하고, 둘째, "end" 로그의 타임스탬프는 해당 시각의 끝을 의미하므로 (num + 1) - prev처럼 1을 더해 포괄적으로 계산해야 한다는 점입니다. 시간 복잡도는 로그 개수를 L이라 할 때 O(L), 공간 복잡도는 최대 중첩 깊이만큼의 스택 공간이 필요해 O(n)입니다.