문제 접근 방법

• 문제 풀기전에 어떻게 할까? 생각하자.

나의 접근 법

: 기존 문자열 s를 가지고 진행했다.
그러면 아래와 같은 현상? 이 발생한다.

• 1번 입력을 보면, 1번째 인덱스에서 발견한다. PPAP를 제거하고, 1번 인덱스에다가 P를 채운다.
  그리고 이번에는 0번 인덱스에서부터 접근을 해야 한다.

• -> 그렇다는 것은 ppap 를 제거 한 후에 인덱스를 다시 앞으로 돌려놓고 탐색을 해야 한다. 는 것을 의미한다.
  문자열 최대길이 n은 100만이다.

• 입력 1번 처럼 생각한다면
  ppppppppppppppppp ppap apapapapapapapapapapap

• 지금 100만도 아니지만, 인덱스를 앞으로 오면서 진행하는 구조이다.

• 만약에 100만 - 4자리에서 ppap가 발결 되었다.
  그런데 앞에서 ppa 이다. 그러면 p가 뒤에 추가되고
  이에 대한 처리를 해야 한다.

코드를 생각해보면,

기존의 s를 가지고 진행한다고 생각해보면
for문 돌리다가 erase를 한 다음에 insert를 해야 한다.

• insert의 시간복잡도는 n이다. 그러면 for문 안에서 insert를 하는 것이므로 이때의 시간복잡도는 n 제곱이다.

n이 100만이므로 시간초과를 간단하게 생각할 수 있다.
다른 해결 전략을 생각해야 한다.

자료 구조가 깨질까???

• stl 오류발생할까?
  : 오류 발생하지 않는다.
  -> for 순회 중에 erase 를 해보면서 하는 코드이다.

• 뭔가 좀 문제가 될 거 같으면 다른 방법을 생각해보자..

위의 코드는 시간초과다.

• 왜냐하면 발견할때마다 0번 인덱스에서부터 시작하기 때문에

접근방법 다르게 하자.

• 위의 문제에서 처럼 기존의 s를 변경하려고 하지 말고,
  새로운 자료구조를 가지고 와서 s를 가지고 뭔가를 하려고 하면 편하게 처리할 수 있지 않을까? 를 생각할 수 있따.

• 기존의 s를 가지고 처리하기에는 아래의 코드처럼 인덱스를 정리하는 등의 작업을 추가로 해야 하는 불편함이 발생한다.
  

---

string에서의 erase 와 insert는 순차열 컨테이너와 다르다.

https://velog.io/@kwt0124/string-substr

---