[2025.02.07] 햄버거 만들기

문제 설명

햄버거 가게에서 일을 하는 상수는 햄버거를 포장하는 일을 합니다. 함께 일을 하는 다른 직원들이 햄버거에 들어갈 재료를 조리해 주면 조리된 순서대로 상수 앞에 아래서부터 위로 쌓이게 되고, 상수는 순서에 맞게 쌓여서 완성된 햄버거를 따로 옮겨 포장을 하게 됩니다. 상수가 일하는 가게는 정해진 순서(아래서부터, 빵 - 야채 - 고기 - 빵)로 쌓인 햄버거만 포장을 합니다. 상수는 손이 굉장히 빠르기 때문에 상수가 포장하는 동안 속 재료가 추가적으로 들어오는 일은 없으며, 재료의 높이는 무시하여 재료가 높이 쌓여서 일이 힘들어지는 경우는 없습니다.

 

예를 들어, 상수의 앞에 쌓이는 재료의 순서가 [야채, 빵, 빵, 야채, 고기, 빵, 야채, 고기, 빵]일 때, 상수는 여섯 번째 재료가 쌓였을 때, 세 번째 재료부터 여섯 번째 재료를 이용하여 햄버거를 포장하고, 아홉 번째 재료가 쌓였을 때, 두 번째 재료와 일곱 번째 재료부터 아홉 번째 재료를 이용하여 햄버거를 포장합니다. 즉, 2개의 햄버거를 포장하게 됩니다.

 

상수에게 전해지는 재료의 정보를 나타내는 정수 배열 ingredient가 주어졌을 때 상수가 포장하는 햄버거의 개수를 return 하도록 solution 함수를 완성하시오.

 

 

제한사항

• 1<=ingredient의 길이<=1,000,000
• ingredient의 원소는 1, 2, 3 중 하나의 값이며, 순서대로 빵, 야채, 고기를 의미합니다.

 

 

입출력 예

ingredient			result	설명
[2, 1, 1, 2, 3, 1, 2, 3, 1]			2	문제 예시와 같습니다.
[1, 3, 2, 1, 2, 1, 3, 1, 2]			0	상수가 포장할 수 있는 햄버거가 없습니다.

 

 

문제 풀이

풀이 언어 : C++

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> ingredient) {
    int answer = 0; // 포장한 햄버거 수
    vector<int> hamberger={1, 2, 3, 1}; // 햄버거 포장 순서
    vector<int> table; // 작업대
    
    for(int i=0; i<ingredient.size(); i++)
    {
        // 테이블에 재료 쌓기
        table.push_back(ingredient[i]);
        
        // 쌓인 재료가 4개 이상이라면 포장가능한지 확인
        if(table.size()>=4)
        {
            bool enable_packed=true; // 포장 가능 표시 변수
            
            // 포장 가능한지 확인
            for(int i=0; i<hamberger.size(); i++)
            {
                // 햄버거 재료 순서와 테이블 재료 순서가 다르면
                if(hamberger[hamberger.size()-1-i]!=table[table.size()-1-i])
                {
                    // 포장 불가
                    enable_packed = false;
                    break;
                }
            }
            
            // 포장 가능하다면
            if(enable_packed)
            {
                // 포장하기
                table.pop_back();
                table.pop_back();
                table.pop_back();
                table.pop_back();
                
                // 햄버거 포장 개수 업데이트
                answer++; 
            }
        }
    }
    return answer;
}

테이블 놓을 생각을 못하고 풀었을 때는 어려울 것 같았는데 테이블 하나 놓으니 생각보다 직관적으로 풀 수 있었다.

 

먼저 햄버거 재료를 쌓는 순서를 저장하고 있는 hamberger int형 벡터를 선언해주고 알맞은 순서로 초기화해준다. 문제에서 빵-야채-고기-빵 순서로 쌓인 햄버거만 포장한다고 하니 그 순서대로 재료 번호를 초기화한다. 그리고 table이라는 이름의 작업대를 하나 만들어 준다. 마찬가지로 int형 벡터이다. 앞으로 이 작업대에 재료를 순서대로 쌓아올리고 포장도 할 것이다.

 

for문을 이용해 모든 재료를 순회해준다. 그리고 순회하면서 세 가지 작업을 수행한다.

• 작업대에 재료 하나 쌓기
• 쌓인 재료가 4개 이상이면 포장가능한지 확인하기
• 포장이 가능하다면 햄버거 포장하고 포장 개수 업데이트하기

이렇게 세 가지 작업을 for문 안에서 수행하게 될 것이다.

 

먼저 push_back()함수를 이용해 ingredient에 있는 순서대로 table에 재료를 하나 쌓는다.

그리고 작업대에 쌓인 재료들이 4개 이상인지 확인한다. 적어도 4개는 있어야 햄버거를 하나 만들어 포장할 수 있기 때문이다. 4개가 넘지 않는다면 다음 재료를 올리기 우해 반복문이 한번 돌아가고 4개이상일 경우는 햄버거를 만들 수 있는 상태인지 확인해야 한다.

 

햄버거를 만들 수 있는 상태인지 확인하는 방법은 이렇다. 먼저 포장 가능, 불가능을 나타내는 bool타입 변수 enable_packed를 선언하고 true로 초기화한다. 이제 본격적으로 포장이 가능한지 확인하면 된다.

for문을 이용해 아까 저장해두었던 hamberger의 재료 순서와 작업대 위에 쌓인 재료의 순서를 비교한다. 단 작업대의 가장 마지막에 올라온 재료부터 이전에 올라온 재료 순서대로 확인해야 한다. 즉, 쌓여있는 재료를 위에서부터 확인한다는 뜻이다. 당연히 재료 순서를 표시한 hamberger도 뒤에서부터 확인해야 한다.

두 재료 순서가 완전히 같아 enable_packed가 변경되지 않고 이 코드를 지나간다면 enable_packed는 true가 되는 것이고 그게 아닐 경우 enable_packed는 false로 바뀌고 반복문은 중단한다.

 

이제 enable_packed 값을 확인하여 true라면 햄버거를 포장하면 된다. 포장하는 방법은 간단하다. 작업대에서 빼주면 되는 것이다. pop_back() 함수를 이용하여 위에서부터 4개의 재료를 빼준다. 그리고 마지막으로 햄버거 포장 개수를 나타내는 answer를 업데이트해준다.

 

이렇게해서 반복문이 모두 돌아 모든 재료를 작업대에 올려보고 나면 answer에 답이 결졍되게 된다.

 

 

오답 노트

포장이 가능하지 확인하는 코드를 함수로 만들어서 호출하여 사용했었는데 시간 초과가 발생하였다. 함수에 있던 내용을 그대로 solution 함수로 옮겨서 사용하니 해결되었다.

// 현재 위치부터 햄버거를 포장할 조건이 되는지 확인하는 함수
bool check_packed(int index, vector<int> table)
{
    vector<int> hamberger={1, 2, 3, 1};
    for(int i=0; i<hamberger.size(); i++)
    {
        if(hamberger[hamberger.size()-1-i]!=table[index-i])
        {
            return false;
        }
    }
    
    return true;
}

 

 

문제 링크

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

프로그래머스