<프로그래머스 C++> 햄버거 만들기 풀이

문제

재료가 순서대로 쌓이고, 아래서부터 빵(1) - 야채(2) - 고기(3) - 빵(1) 순서로 쌓인 햄버거만 포장한다.

포장한 햄버거의 개수를 return하는 문제이다.

 

햄버거를 포장하면 해당 재료들을 제거하고, 남은 재료 위에 계속 쌓인다.

 

예시

ingredient	result
[2, 1, 1, 2, 3, 1, 2, 3, 1]	2
[1, 3, 2, 1, 2, 1, 3, 1, 2]	0

---

문제 흐름 파악

재료를 순서대로 쌓고, 완성 패턴인 [1, 2, 3, 1]이 맨 위에 만들어지면 제거하는 구조이다.

 

이 문제 해결 방식으로는 스택의 원리를 이용했다. Vector를 스택처럼 사용해서 맨 위에 완성 패턴이 쌓이게 되면, pop_back()을 이용해서 후입선출(LIFO)의 원리를 이용했다.

---

문제 풀이

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

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

    for(int i = 0; i < ingredient.size(); ++i)
    {
        stk.push_back(ingredient[i]);
        int n = stk.size();

        if(n >= 4 &&
           stk[n-4] == 1 &&
           stk[n-3] == 2 &&
           stk[n-2] == 3 &&
           stk[n-1] == 1)
        {
            ++answer;
            stk.pop_back();
            stk.pop_back();
            stk.pop_back();
            stk.pop_back();
        }
    }
    return answer;
}

---

코드 흐름

1. 재료 쌓기

stk.push_back(ingredient[i]);
int n = stk.size();

재료를 하나씩 새로 만든 vector인 stk에 push한다.

 

2. 햄버거 완성 체크

if(n >= 4 &&
   stk[n-4] == 1 &&
   stk[n-3] == 2 &&
   stk[n-2] == 3 &&
   stk[n-1] == 1)

반복문 안에 조건문을 넣어 벡터에 하나씩 추가될 때 마다 맨 위 4개가 완성 패턴[1, 2, 3, 1]인지 확인한다.

 

n>=4 조건을 확인해서 범위에 맞는지도 같이 확인해서 안전하게 작성했다.

---

3. 햄버거 제거

++answer;
stk.pop_back();
stk.pop_back();
stk.pop_back();
stk.pop_back();

패턴이 완성되면 출력할 답인 answer를 하나 증가시키고, 그 완성 패턴을 pop_back으로 제거한다.

 

제거 후엔 그 다음의 재료를 계속 추가한다.

---

예시 흐름

push(2) → [2]            패스
push(1) → [2, 1]         패스
push(1) → [2, 1, 1]      패스
push(2) → [2, 1, 1, 2]   stk[0]=2   패스
push(3) → [2, 1, 1, 2, 3] stk[2]=1  패스
push(1) → [2, 1, 1, 2, 3, 1]
          stk[2]=1  stk[3]=2  stk[4]=3  stk[5]=1 
          → answer=1, pop 4번 → [2, 1]

예시 문제를 이 코드에 대입해서 넣어보면 이런 흐름이 이루어진다.

---

핵심 포인트

1. vector를 스택처럼 사용해 후입선출의 원리를 이용한다.

 

2. push_back 이후 n = stk.size()를 계산해야 방금 push한 원소가 stk[n-1]이 된다.

 

3. 햄버거를 제거하면 남은 재료가 자연스럽게 이어지므로 연쇄적으로 자동으로 처리된다.