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

✅ LV.1

✏️ 1차 솔루션

1. ingredient vector 를 string 형으로 변환
2. ingredient 문자열 길이가 4보다 작아질 때까지 for 문으로 문자 탐색해서 빵-야채-고기-빵 조합인 "1231" 찾으면 햄버거 개수 더하기
   ➡️ 해당 자리부터 4자리의 문자열이 "1231" 이라면 해당 자리부터 4자리를 erase 로 지우기

📌 self feedback

일단 vector 를 처음부터 끝까지 string 에 저장을 하고 그 후에 또 탐색을 하면 시간이 소요
각 자리마다 완전탐색을 하면서 햄버거 조합을 찾아야하기 때문에 시간복잡도가 큼

✏️ 2차 솔루션

stack 의 원리를 차용
1. ingredient vector 를 string 형으로 변환
2. 동시에 ingredient 가 빵(1)이고 stack 의 크기가 4보다 크면 문자열 뒤 4자리가 빵-야채-고기-빵 조합인 "1231" 인지 확인
3. 빵-야채-고기-빵 조합 찾으면 문자열 뒤 4자리 erase 로 지우기

✏️ 최종 솔루션

1. ingredient가 빵(1)이면 vector<int> v 에 ingredient를 push_back
2. v.back() 이 빵(1)이고 현재 재료 x 가 야채(2)이면 햄버거 가능성 있으므로 빵(1)을 빵+야채(12)로 갱신 ➡️ 이 과정을 햄버거 하나 완성할 수 있을 때까지 반복
3. 햄버거를 완성할 수 있는 것은 v.back() 이 빵+야채+고기(123)이고 현재 재료 x 가 빵(1)인 경우이므로 이 때는 햄버거 개수 더해주고 완성한 햄버거 재료는 v.pop_back() 해주면 햄버거에 사용되지 않은 재료만 남게 되고 계속해서 햄버거 만들 수 있음

📌 self feedback

2차 솔루션은 1차 솔루션에 비해 시간을 절약할 수 있음 ➡️ 전체 ingredient를 모두 탐색하지 않고 햄버거가 완성될 가능성이 있는 경우에 한해 현재까지 저장된 ingredient 끝 4자리만 확인하면 되기 때문

✏️ code

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

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

    return answer;
}