Lv1_[햄버거 만들기, C++] 알고리즘 정리 - 프로그래머스

(빵 – 야채 – 고기 - 빵) 순서로 햄버거 만들기!

문제 내용, 조건, 예시는 프로그래머스 사이트 참조

---

제시한 조건을 보면 stack 구조를 사용하는 것이 가장 효율적이라 생각합니다.

아래의 그림과 같이 햄버거 틀(vector<int>)를 만들어서 햄버거 재료를 차곡 차곡 쌓는 방식을 만들어줌
햄버거가 만들어지기 전에 다른 재료들도 들어올 수 있기 때문에 햄버거 틀을 여러개 생성할 수 있도록 햄버거 틀 묶음(vector<vector<int>>)을 구성해줌

ex) ingredient = {1, 2, 3, 1} 들어온다면

햄버거 1개를 완성 시킬 수 있다.


ex) ingredient = { 1, 2, 1, 3, 1, 1, 2, 3, 1, 2, 3, 1 } 들어온다면

앞쪽 { 1, 2, 1, 3 } 재료는 손실되고 2개의 햄버거를 만들 수 있다.

위와 같은 알고리즘을 가지기 위한 조건

1) 불필요한 반복을 줄이기 위해 2차원 벡터를 stack처럼 사용함
- 시간 복잡도 n

2) 재료 [1-2-3-1] 순서가 아닌 다른 순서로 들어오면 햄버거를 완성시키지 못함
2-1) 이전에 저장되고 있던 재료들도 햄버거를 만들지 못하기 때문에 모든 햄버거 틀을 비워줌
2-2) 다른 순서로 들어온 재료가 1(빵)이면 비우지 않고 다음 햄버거 틀에 넣어줌

3) 햄버거가 완성되면 바로 포장해준다.
3-1) 비워준 햄버거 틀 이전에 미완성된 햄버거가 있으면 위치를 옮겨서 다시 햄버거를 만듦

4) 재료가 1,000,000개를 넘어서면 햄버거 제작을 멈춤

소스코드

int solution(vector<int> ingredient) {
        int answer = 0;
        int made_count = 1;         // 사용한 재료수
        int max_count = 1000000;    // 재료의 최대 개수
 
        // 햄버거 저장틀 (2차원 벡터)
        std::vector<std::vector<int>> hamburger_stack;    // 1)
        // 햄버거 제작 방법(해당부분면 변경하면 다양한 햄버거를 만들 수 있음)
        std::vector<unsigned int> hamburger_OrderToMake = { 1, 2, 3, 1 };
        int hamburger_OrderToMake_size = hamburger_OrderToMake.size();
             
        for (int item : ingredient) {
            if(made_count > max_count) {    // 4)
              break;
            } 
            made_count++;
            
            unsigned int hamburger_stack_size = hamburger_stack.size();
 
            if(hamburger_stack_size == 0) {
                std::vector<int> hamburger_OrderTmp;
                hamburger_stack.push_back(hamburger_OrderTmp);
                hamburger_stack_size++;
            }
 
            // 햄버거 틀에 조건에 맞춰 넣는 곳
            std::vector<int> &tmpVector = hamburger_stack[hamburger_stack_size-1];
            unsigned int hamburger_OrderTmp_size = tmpVector.size();
            if(hamburger_OrderToMake[hamburger_OrderTmp_size] == item) {    // 2)
                tmpVector.push_back(item);
                if(tmpVector.size() == hamburger_OrderToMake_size) { // 3)
                    answer++;
                    hamburger_stack.erase(hamburger_stack.end()-1);
                }
            } else {
                if(item == hamburger_OrderToMake[0]) {              // 2-2)
                    std::vector<int> hamburger_OrderTmp = {item};
                    hamburger_stack.push_back(hamburger_OrderTmp);
                } else {
                    hamburger_stack.clear();                        // 2-1)
                }
            }
        }
 
        return answer;
    }

테스트 속도도 잘 나온 편으로 생각이 든다.

↓↓↓↓↓↓ 유익했다면 하트 뿅 ♥ ↓↓↓↓↓↓