[프로그래머스/Day 22] 햄버거 만들기 - 스택을 사용하는 이유

프로그래머스 '햄버거 만들기' 문제를 풀면서 겪었던 std::find 기반 탐색의 문제점과 이를 스택(Stack) 구조로 변경하여 $O(N)$으로 최적화한 과정을 정리해 봅니다.

1. 문제 분석 및 핵심 조건

이 문제의 목표는 주어진 재료 배열(ingredient)에서 정해진 순서인 [빵(1) - 야채(2) - 고기(3) - 빵(1)] 패턴을 찾아 햄버거를 몇 개 포장할 수 있는지 세는 것입니다.

• 순서 중요: 반드시 1-2-3-1 순서로 쌓여야만 포장할 수 있습니다.
• 재료 소거: 햄버거가 완성되어 포장되면 해당 재료 4개는 사라집니다. 이때, 사라진 재료의 위와 아래에 있던 재료들이 합쳐지며 새로운 1-2-3-1 패턴을 만들 수도 있습니다.
• 입력 크기: 재료의 개수는 최대 1,000,000개입니다. 알고리즘으로는 시간 초과가 발생할 수 있어 효율적인 접근이 필요합니다.

---

2. 초기 접근 및 시행착오

처음에는 std::find를 사용하여 특정 재료를 순서대로 찾고, 상태 변수(trueCount)를 두어 1→2 → 3 → 1 순서를 맞추는 방식을 시도했습니다.

발생했던 문제점:

1. 복잡한 인덱스 관리 (Index Out of Bounds):
   find로 찾은 위치를 기준으로 다음 재료를 탐색하다 보니, 인덱스가 뒤죽박죽이 되기 쉬웠습니다. 특히 중간에 재료를 건너뛰거나 탐색 범위를 지정할 때, 벡터의 끝(end())을 넘어가는 범위 참조 오류가 발생하기 쉬운 구조였습니다.
2. 비효율적인 반복 탐색 (Time Limit Exceeded):
   while 루프 안에서 매번 find를 호출하면 최악의 경우 벡터를 계속해서 처음부터 훑어야 합니다. 재료가 최대 100만 개인 상황에서 이러한 수준의 탐색 방식은 시간 초과(Time Limit)로 이어질 수밖에 없었습니다.
3. 상태 관리의 어려움:
   '현재 빵을 찾았는지', '야채를 찾았는지'를 변수로 따로 관리하다 보니 코드가 길어지고, 예외 상황(중간에 패턴이 끊기는 경우 등)을 처리하기가 매우 까다로웠습니다.

---

3. 해결 전략: 스택 활용

문제를 단순화하면 "재료를 순서대로 쌓다가, 끝부분이 1-2-3-1이 되면 치운다"는 것입니다. 이는 스택 자료구조의 특성과 정확히 일치합니다.

1. 순차 탐색: 재료(ingredient)를 처음부터 하나씩 가져옵니다.
2. 스택(Vector)에 저장: 가져온 재료를 새로운 벡터(hamburgerMaker)에 차곡차곡 쌓습니다 (push_back).
3. 패턴 확인: 벡터에 재료가 4개 이상 쌓였을 때, 가장 최근에 쌓인 4개가 [1, 2, 3, 1]인지 확인합니다.
4. 포장(Pop): 패턴이 맞다면 카운트를 증가시키고, 벡터에서 해당 4개를 제거합니다.

이 방식을 사용하면 복잡하게 인덱스를 계산하거나 find로 탐색할 필요 없이, 한 번의 순회() 만에 문제를 해결할 수 있습니다.

---

4. 코드 구현

최종적으로 작성한 코드입니다. std::vector를 스택처럼 활용하였으며, reserve와 resize를 통해 성능을 극대화했습니다.

#include <vector>

using namespace std;

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

    // [최적화 1] 불필요한 재할당을 막기 위해 메모리 미리 확보
    hamburgerMaker.reserve(ingredient.size()); 

    for (int i : ingredient) {
        hamburgerMaker.push_back(i);
        int size = hamburgerMaker.size();

        // [최적화 2] 4개 이상이고, 마지막 재료가 빵(1)일 때만 검사 (Fast Fail)
        if (size >= 4 && hamburgerMaker.back() == 1) { 
            if (hamburgerMaker[size - 4] == 1 && 
                hamburgerMaker[size - 3] == 2 && 
                hamburgerMaker[size - 2] == 3)
            {
                answer++;
                // [최적화 3] pop_back 4번 대신 resize로 한 번에 처리
                hamburgerMaker.resize(size - 4); 
            }
        }
    }

    return answer;
}

---

5. 복기 및 확장

이 코드는 다음과 같은 장점이 있습니다.

1. 시간 복잡도 : ingredient를 단 한 번만 순회합니다. push_back과 resize는 분할 상환(Amortized) $O(1)$이므로 매우 빠릅니다.
2. reserve() 활용: 벡터는 공간이 부족하면 메모리를 재할당하고 데이터를 복사합니다. reserve(ingredient.size())를 통해 이 비용을 없앴습니다.
3. resize() 활용: pop_back()을 4번 호출하는 것보다 resize(size - 4)를 호출하는 것이 함수 호출 비용을 줄이고, "4개를 한 번에 제거한다"는 의미를 더 명확하게 전달합니다.
4. 조건문 최적화: hamburgerMaker.back() == 1 조건을 먼저 검사하여, 마지막이 빵이 아닌 경우 불필요한 앞 재료 비교 연산을 수행하지 않도록 했습니다.

초기의 복잡한 find 탐색 방식에서 벗어나, 자료구조(스택)의 특성을 문제에 맞게 잘 활용하면 코드가 얼마나 간결하고 강력해질 수 있는지 확인할 수 있었습니다.