[프로그래머스] Lv.1 햄버거 만들기 c++

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

프로그래머스

햄버거 가게에서 일하는 상수는 정해진 순서로 쌓인 재료를 사용해 햄버거를 포장합니다.

햄버거를 만들기 위한 재료의 순서는 다음과 같습니다:

• 빵(1) → 야채(2) → 고기(3) → 빵(1)

재료는 조리된 순서대로 쌓이며, 상수는 정해진 순서에 맞는 재료로만 햄버거를 만들 수 있습니다.

재료가 추가적으로 쌓이는 동안 속도에 제한은 없으며, 재료의 높이는 무시됩니다.

최대로 만들 수 있는 햄버거 개수를 구해야 합니다.

 

풀이 방법

스택의 원리를 활용하면 이 문제를 쉽게 풀 수 있습니다.

예를 들어, [2, 1, 1, 2, 3, 1, 2, 3, 1]라는 배열이 주어졌다고 가정해 봅시다.

배열이 쌓이는 순서를 보면, 처음에 [2, 1, 1, 2, 3, 1]에서 햄버거를 만들고 나머지 재료로 [2, 1, 2, 3, 1]이 남습니다.

이후 남은 재료로 다시 햄버거를 만들 수 있습니다. 이처럼 재료를 순차적으로 처리하며 햄버거를 만들면 됩니다.

 

다만, 여기서 중요한 점은 배열의 최대 길이가 100만 개라는 것입니다.

만약 단순히 for문을 사용하여 모든 재료를 매번 확인한다면, 시간 복잡도가 O(n^2)으로 시간초과가 납니다.

 

그러므로 이 문제에서는 재료가 위로 쌓이는 특성을 활용하여 벡터를 스택처럼 사용합니다.

재료를 순차적으로 벡터에 추가하면서, 빵(1) → 야채(2) → 고기(3) → 빵(1) 순서가 쌓였을 때

해당 요소들을 pop하여 제거합니다.

 

풀이 코드

#include <string>
#include <vector>

using namespace std;

vector<int> hamburger;
int solution(vector<int> ingredient) {
    int answer = 0;
    
    for(int item : ingredient){
        hamburger.push_back(item);
        int size = hamburger.size();
        
        if(size>=4){
            if(hamburger[size-4] == 1 && hamburger[size-3] == 2 &&
            hamburger[size-2] == 3 &&hamburger[size-1] == 1){
                
                hamburger.pop_back();
                hamburger.pop_back();
                hamburger.pop_back();
                hamburger.pop_back();
                answer++;
            }
        }
    }
    return answer;
}