프로그래머스 133502 - 햄버거 만들기 Lv.1

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

// 프로그래머스 133502 - 햄버거 만들기 Lv.1
// https://school.programmers.co.kr/learn/courses/30/lessons/133502

// 문제 설명
// 재료(1=빵, 2=야채, 3=고기)가 아래서부터 위로 쌓인다.
// 아래->위로 빵-야채-고기-빵 (1,2,3,1) 순서가 만들어지면 그 4개를 포장한다.
// 포장으로 4개가 빠지면 그 위아래 재료가 새로 맞닿아 또 햄버거가 될 수 있다.
// 포장한 햄버거의 총 개수를 구한다.
// 예) [2,1,1,2,3,1,2,3,1] -> 2

// 제약 조건
// 1 <= ingredient 길이 <= 1,000,000 (원소는 1,2,3)

// 접근
// 스택으로 재료를 쌓되, 새 재료를 push할 때마다 위 4개를 확인한다.
// 핵심은 "4개를 빼면 그 자리에서 다시 위아래가 붙는다"는 점인데,
// 스택이라면 pop 후 새로 들어오는 값이 자연스럽게 이전 재료 위에 이어져
// 별도 재배치 없이 연쇄 포장이 처리된다.
// 매 원소를 한 번 push, 조건 성립 시 한 번 제거하므로 시간 O(n).

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> ingredient)
{
    int answer = 0;

    vector<int> st;                 // 쌓이는 재료 스택
    for (int x : ingredient)
    {
        st.push_back(x);
        int n = st.size();
        // 위 4개가 아래->위로 빵(1)-야채(2)-고기(3)-빵(1)인지 확인
        if (n >= 4 &&
            st[n - 1] == 1 && st[n - 2] == 3 &&
            st[n - 3] == 2 && st[n - 4] == 1)
        {
            st.resize(n - 4);       // 완성된 4개 제거
            answer++;
        }
    }

    return answer;
}

정리

• 스택 top 4개만 보면 되므로 매번 전체를 훑을 필요가 없다.
• vector를 스택처럼 쓰면 resize(n-4)로 4개를 한 번에 빼고, 다음 push_back이 그 위에 이어져 연쇄 포장이 공짜로 해결된다.
• 인덱스로 위에서부터 [n-1], [n-2], [n-3], [n-4]를 비교하면 순서가 한눈에 들어온다.
• 길이가 최대 100만이라 O(n) 한 번 순회로 충분하다.