문제 133502. 햄버거 만들기

문제 링크

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

프로그래머스

 

 

 

난이도 : Lv.1  

 

문제 요약 설명

상수가 햄버거를 포장하는 일을 합니다. 상수는 정해진 순서(아래서부터, 빵-야채-고기-빵)로 쌓인 햄버거만 포장을 합니다. 상수에게 전해지는 재료의 정보를 나타내는 정수 배열 ingredient가 주어졌을 때, 상수가 포장하는 햄버거의 개수를 return 하도록 solution 함수를 완성하시오.

입력

• 재료의 정보를 나타내는 정수 배열 ingredient

 

입력 제한

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

입력 예제

// input
[2, 1, 1, 2, 3, 1, 2, 3, 1] // ingredient

// ans
2

 

풀이 방식

해당 문제는 ingredient에 1, 2, 3, 1순서가 만들어졌을 때 햄버거 하나를 만들 수 있다. 다만, 주의해야 하는 점은 햄버거 재료로 사용된 재료는 ingredient배열에서 제외해야한다는 것이다. 따라서, 다음과 같은 규칙을 따르며 스택으로 햄버거를 찾는다.

• 스택의 각각의 데이터는 재료의 종류를 저장하며, 1, 2, 3, 1패턴 중 몇번째 단계(step)까지 왔는지 또한 같이 저장한다. 
• 현재 재료의 step을 결정하는 방법은 이전 재료의 종류와 단계를 보고 판단한다. 현재 재료가 이전 재료에 연결되는 패턴이라면 이전 재료의 단계 + 1로 저장하고, 그렇지 않다면 0단계로 저장한다. (단, 현재 재료가 1(빵)인 경우 1단계로 저장)
• 만약, 해당 패턴이 완성되었다면, 만들 수 있는 햄버거 개수를 저장하는 answer를 1증가시키고, 사용한 재료들을 stack에서 pop으로 제거한다.

 

정답 코드 

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

using namespace std;

struct stack_data{
    int ingre;
    int step;
};

int solution(vector<int> ingredient) {
    int answer = 0;
    stack<stack_data> s;
    
    for(int elem : ingredient){
        // 스택이 비어있는 경우.
        if(s.empty()){
            if(elem == 1) s.push({elem, 1});
            else s.push({elem, 0});                     
            continue;
        }
                
        stack_data prev = s.top();
        
        // 이전에 연결된 상황이고, 현재 재료와 연결될 경우
        if(prev.step > 0 && (prev.ingre % 3 + 1) == elem){ 
            if(elem == 1){
                s.pop(); s.pop(); s.pop();
                answer++;
            }
            else{
                s.push({elem, prev.step+1});    
            }
                   
        }
        else{
            if(elem == 1) s.push({elem, 1});
            else s.push({elem, 0});
        }
    }
    
    cout << 3 % 3 + 1 << '\n';
    return answer;
}