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

🔗알고리즘 문제

시간복잡도를 줄이기 위하여 많은 고민을 하게 된 문제이다. 내 손으로 직접 코드를 수정하고 시간을 줄여 알고리즘을 해결해나가는 과정은 언제나 짜릿한거 같다.

문제 분석

이 문제는 간단하게 설명해서 일정한 int형 배열을 입력받고 햄버거를 얼마나 만들 수 있는지 출력하면 되는 문제이다.

발상 & 알고리즘 설계

for(int element = 0; element < ingredient.size(); element++){
    if(*(first + element) != Recipe[recipeCount])
        recipeCount = 0;

    if(*(first + element) == Recipe[recipeCount]) 
        recipeCount++;
    
    if(recipeCount != 4) continue;

    ingredient.erase(ingredient.begin() + (element - 3), ingredient.begin() + element + 1);
    answer++;
    recipeCount = 0;
    element = -1;
}

내가 처음 작성한 로직으로 인자로 들어온 배열을 쭉 돌며 넣어야 할 재료와 배열의 값이 맞으면 레시피를 한칸 지워주고 이런식으로 쭉 레시피를 채워 레시피가 모두 차면 배열에 해당 부분을 지워주고 다시 이런식으로 반복하는 형식이다.

정답은 맞게 나왔지만 for문을 게속하여 돌리면서 배열의 값도 지워야해 조금만 배열이 커지게 되도 시간이 매우 많이 걸리는 방식이었다.

곰곰히 생각해보니 배열 순서대로 판단하게 되니
2 1 [1 2 3 1] 이러한 방식으로 뒤에 4개만 판단해주어도 같은 값이 나오겠다는 생각이 들었다.

생각대로 로직을 수정하여 문제를 해결하였다.

코드

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

using namespace std;

int solution(vector<int> ingredient);

int main(){
    // Test Code
    vector<int> orderList = {2, 1, 1, 2, 3, 1, 2, 3, 1};

    cout << solution(orderList);
}

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

    for(int element : ingredient){
        recipe.push_back(element);

        if(recipe.size() < 4) continue;

        if(recipe[recipe.size() - 4] == 1 && recipe[recipe.size() - 3] == 2 && recipe[recipe.size() - 2] == 3 && recipe[recipe.size() - 1] == 1){
            recipe = recipe.substr(0, recipe.size() - 4);
            answer++;
        }
    }        

    return answer;
}