해당 코드 시간복잡도, 메모리 사용량 질문드립니다.

Question

큐의 경우 시간복잡도와 메모리 사용량을 어떻게 구해야 하나요?#include #include #include #include using namespace std; typedef struct { int y, sum, flag, cnt; }info; info I; queue q; int arr[200001]; int n = 200000, result = -INT_MAX; void start() { I = { 0,arr[0],0,arr[0] == 0 ? 1 : 0 }; q.push(I); I = { 0,0,1,1 }; q.push(I); while (!q.empty()) { int y = q.front().y; int sum = q.front().sum; int flag = q.front().flag; int cnt = q.front().cnt; q.pop(); int ny = y + 1; if (ny > n) continue; result = max(result, cnt); if (flag) { I = { ny,sum + arr[ny],1,sum + arr[ny] == 0 ? cnt + 1 : cnt }; q.push(I); } else { I = { ny,sum,1,sum == 0 ? cnt + 1 : cnt }; q.push(I); I = { ny,sum + arr[ny],1,sum + arr[ny] == 0 ? cnt + 1 : cnt }; q.push(I); } } cout << result; } int main() { ios::sync_with_stdio(0); cin.tie(0); for (int i = 1; i < 200001; ++i) cin >> arr[i]; start(); }

해당 코드 시간복잡도, 메모리 사용량 질문드립니다.

0개의 답변

기타 목록