프로그래머스 햄버거 만들기 C++

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

프로그래머스

 

처음 작성한 코드

#include <string>
#include <vector>
using namespace std;

int MakeHamburger(int& answer, vector<int>& ingredient){
    for(int i =0; i< ingredient.size() - 3; ++i){
        if(ingredient[i] == 1
          && ingredient[i + 1] == 2
          && ingredient[i + 2] == 3
          && ingredient[i + 3] == 1){
            ++answer;
            ingredient.erase(ingredient.begin() + i, ingredient.begin() + i + 3);
            answer = MakeHamburger(answer, ingredient);
            i += 4;
            break;
        }
    }
    return answer;
}

int solution(vector<int> ingredient) {
    int answer = 0;
    answer = MakeHamburger(answer, ingredient);
    
    return answer;
}

 

erase는 요소를 지운 후 남아있는 요소들을 옮기는 작업까지 하기 때문에 시간이 걸린다.

 

찾아보니 Stack을 활용하라고 한다.

 

정답 코드

#include <string>
#include <vector>
using namespace std;

int solution(vector<int> ingredient) {
    int answer = 0;
    
    vector<int> v = {-1};
    for(int a : ingredient){
        if(v.back() == 1 && a == 2)
            v.back() = 12;
        else if(v.back() == 12 && a == 3)
            v.back() = 123;
        else if(v.back() == 123 && a == 1){
            v.pop_back();
            ++answer;
        }
        else
            v.push_back(a);
    }
    return answer;
}