인프런 커뮤니티 질문&답변

다른질문과 비슷한 질문인데 이해가 잘 안가서 좀 더 자세한 답을 부탁 드리고자 합니다.

#include <bits/stdc++.h>

using namespace std;

int n;

vector<pair<int,int>> v;

int a, b;

priority_queue<int, vector<int>, greater<>> pq;

int ret;

string s,f;

int main()

{

cin >> s>>f;

while (s.find(f) < s.size())

{

int n = s.find(f);

s.erase(n, f.size());

//cout << s<<"\n";

}

if (s.size())

cout << s << "\n";

else

cout << "FRULA" << "\n";

}

제 코두의 경우 시간복잡도가 O(N)이 아니라 O(n^2) 인 이유를 좀만 자세하게 설명해주시면 감사하겠습니다. 비슷한 질문 답변 내용이 이해가 잘 안되서 한 번 더 잘문드립니다.

저는 천만의 경우 1000만 + 999만 999 + ... 1 이라고 생각이 되서요 ㅠㅠ.

while 안에서의 시간복잡도 계산이라 더 이해가 안가는 것 같기도 합니다..