🖊️ 문제

https://school.programmers.co.kr/learn/courses/30/lessons/133502#

🖊️ 풀이

1차

보자마자
stack이다!!!
했는데?
음.. 넣었다뺐다 해야하나? 스택에서 원소 관리가 에반데..
한 번 해보고 장렬히 전사. 시간초과됨

2차

그리고 이 int 벡터를 string 타입으로 바꿔서 find 후 있으면 삭제.
이렇게 해도 시간초과.

3차

아무래도 매 번 find하는게 문제라고 느껴서
조건을 추가함.
근데도 시간초과.

4차

find 자체가 문제인것 같다.
문자열 길이가 엄 ~ 청 긴데 find를 막 하고 있으니...
그래서 그냥
어쨌든간에 스택이잖아?
마지막 4개 원소만 맞는지 비교하면 되니까??!!
substr을 통해 문자열을 잘라서 비교해본다.

성공 ~

진짜.. 시간복잡도에 대해 생각해보게 된 느낌...

🖊️ 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int solution(vector<int> ingredient) {
    int answer = 0;
    string str = "";
    
    for(auto& i : ingredient) {
        str += to_string(i);
        if (str.length() >= 4 && str.back() == '1') {
            if (str.substr(str.length() - 4, str.length()) == "1231") {
                str = str.substr(0, str.length() - 4);
                answer += 1;
            }
        }
    }
    
    return answer;
}