#include <string>
#include <vector>
using namespace std;
int solution(vector<int> v) {
int answer = 0, pos = 0;
string str = "";
for (int i = 0; i < v.size(); i++) str += to_string(v[i]);
while (1) {
int cur = str.find("1231", pos);
if (cur == string::npos)
break;
else {
str.erase(cur, 4);
answer++;
if (cur > 2)
pos = cur - 3;
}
}
return answer;
}
빵 야채 고기 빵 -> 1 2 3 1 패턴이므로 v를 문자열로 전환해서 풀면 좋겠다고 생각했다.
문자열로 전환한 후에 while루프를 돌며 1231을 찾고, 찾았다면 answer를 올린 뒤 찾은 위치부터 4개를 삭제하는 방식으로 하면 쉽게 풀리는 문제였지만, 맨 처음엔 시간초과가 나서 골머리를 앓았다.
고민하던 중 깨달은 것이 str.find()의 시작 위치를 항상 0으로 하고있었기에 항상 불필요한 곳도 순환을 하며 1231을 찾고 있던 것이였다. 그래서 cur이라는 변수를 따로 만들어서 위치를 기억하며 최대한 시간복잡도를 줄이는 방식으로 문제를 해결했다.
·ᴗ·