[C++/PGS] [PCCP 모의고사 #2] 3번 - 카페 확장

 

https://school.programmers.co.kr/learn/courses/15009/lessons/121689

프로그래머스

---

프로그래머스 PCCP 모의고사 2회 - 3번

소요시간 약 14분

자료구조 + 단순 구현, 추정 난이도는 level 2

 

k <= 100, order.size() <= 10,000 이었기 때문에,

시간의 최댓값이 1,000,000이라고 판단하여

반복문을 한번 실행할 때마다 시간을 1초씩 추가시키는 방법이 가능했음!

 

그리고 deque의 push, pop 함수들은 소요시간이 모두 O(1)이기 때문에

자주 해도 시간초과가 나지 않는다 ^-^

물론 큐를 사용하지 않거나 더 효율적인 방법도 있지만, 직관적으로 해결했다

 

범위가 더 컸다면 time을 1초씩 증가시키지 않고

-> 음료 제작시간 단위로 증가시키면서 시간을 체크하고, 시간이 일정 값보다 크면 손님을 새로 받는 방식으로 해야할 것

 

 

나의 풀이

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

int solution(vector<int> menu, vector<int> order, int k) {
    int answer = 0;
    int time = 0; // 현재 시간
    int idx = 0; // 주문 번호
    deque<pair<int, int>> dq; // {메뉴번호, 진행상황(시간)}
    while(idx < order.size()){
        if(time%k == 0){ // 손님 새로 방문
            int menuNum = order[idx];
            dq.push_back({menuNum,0});
            idx++;
            if(answer < dq.size()) answer = dq.size();
        }
        time++; // 1초 지남
        if(!dq.empty()){ // 음료 제작
            pair<int,int> now = dq.front();
            dq.pop_front();
            now.second++; // 진행상황 1초 추가
            dq.push_front(now);
            if(now.second==menu[now.first]){ // 제작 완료 시
                dq.pop_front();
            }
        }
    }
    return answer;
}