햄버거 만들기

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

 

 

*초기 작성 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> ingredient) {
    int answer = 0;
    vector<int> pattern = { 1,2,3,1 };

    int i = 0;
    while (i <= ingredient.size() - 4 && ingredient.size() >= 4)
    {
        if (i + 4 <= ingredient.size() && equal(ingredient.begin() + i, ingredient.begin() + (i + 4), pattern.begin()))
        {
            answer++;
            ingredient.erase(ingredient.begin() + i, ingredient.begin() + (i + 4));
            if (i >= 3)
            {
                i -= 3;
            }
            else
            {
                i = 0;
            }
        }
        else
        {
            i++;
        }
    }

    return answer;
}

초기 코드에서의 문제점

 

erase 의 성능 문제:

• 1,2,3,1의 패턴이 발생하면 ingredient vector 배열을 erase하며 answer의 값을 카운팅해주었다.
• erase를 할 때마다 데이터를 삭제하고, 삭제된 이후 모든 데이터가 이동해야함으로 O(n)의 추가 비용 발생.
• ingredient의 크기가 변경될 때, 메모리를 다시 할당하고 데이터를 복사하는 과정이 빈번하게 발생할 수 있음.

불필요한 루프 조건 검색:

• 패턴을 발견할 때마다, erase로 인해 ingredient 배열의 크기가 줄어들어 매번 반복 조건을 다시 계산해야함.

 

---

 

정리하면 erase 함수로 ingredient 배열의 크기가 변경되면 메모리 재할당이 빈번하게 발생할 수 있고, 데이터가 삭제된 이후 뒤의 데이터들을 모두 이동시켜주어야 되기 때문에 불필요한 복사가 이루어진다.

 

 

 

---

 

 

 

*수정된 코드

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

int solution(vector<int> ingredient) 
{
    int answer = 0;
    stack<int> check_list;
    check_list.push(-1);

    for (int i : ingredient)
    {
        if (check_list.top() == 1 && i == 2) check_list.top() = 12;
        else if (check_list.top() == 12 && i == 3) check_list.top() = 123;
        else if (check_list.top() == 123 && i == 1) answer++, check_list.pop();
        else check_list.push(i);
    }

    return answer;
}

 

수정된 코드의 개선점

• 한 번의 루프에서 조건에 맞는 stack의 top 값만 변경되거나 값이 추가.
• ingredient 배열의 데이터 이동, 삭제 없으므로 메모리 재할당 낮음.
• 간단하고 직관적이다.