[PCCP 모의고사 #2] 카페 확장 c++ (큐)

문제 링크

 

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

프로그래머스

 

문제 풀이

이런류의 문제는 너무 반례가 많이 생겨서 왠만하면 노가다로 푸는게 가장 안전한 것 같다. ( 예상치 못한 케이스 걸릴 바엔.. ) 

결국 매번 고객이 진입하는 시간마다,  해당 고객을 포함해서 몇명의 고객이 매장 내 있는지 구하고, 그 중 최대 값을 출력하였다.

 

고객이 진입하는 시간대의 총 인원 수만 고려해도 최대 인원이 나오는 이유는?
'인원이 추가되는 시간' 이기 때문이다. 이후론 이 시간대 외엔 인원이 감소할 가능성 밖에 없다.

 

 

정답 코드

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

int solution(vector<int> menu, vector<int> order, int k) {
    int answer = 1;
    queue<int> qu;
    
    for(int i=0;i<order.size();i++){
        qu.push(i*k);//각손님 진입 시간.
    }
    int end_time=0;
    int it=0;
    int num=0;
    queue<int> waiting;
    while(!qu.empty()){
        int arrive_time=qu.front();
        qu.pop();
        while(!waiting.empty()){
            int f=waiting.front();
            if(f<=arrive_time){
                waiting.pop();
                num--;
            }
            else break;
        }
        num++;
        if(end_time>arrive_time){ //아직 앞주문 종료 x
            end_time+=menu[order[it]];
            waiting.push(end_time);
        }
        else{//앞에 주문 존재x,  바로 주문
            end_time=arrive_time+menu[order[it]];//
            waiting.push(end_time);
           
        }
        
        if(answer<num) answer=num;
        
        
        
        it++;//손님 번호 (0~n-1)
    }
    return answer;
}

 

 

주의

이런식의 문제가 자칫하면 매우 머리아파지는 건, 결국 겹치는 시점에 대한 예외처리인 것 같다.

만약 n초에 Sam이라는 고객이 음료를 받고 나가는데, Tom이 동시에 들어오려 한다면 어떻게 처리해야할까? 에 대한 조건이 문제에 나와 있기에, 이를 잘 고려해서 구현하자. 

나의 경우, 아래와 같이 각 고객이 들어온 시점과 상품을 받는 시점이 같은 고객은 숫자에서 제외하도록 처리해서 해결했다. 

while(!waiting.empty()){
            int f=waiting.front();
            if(f<=arrive_time){ // 들어오는 인원과 동일한 시간에 나가는 고객은 이 시점에 나갔다고 처리
                waiting.pop();
                num--;
            }
            else break;
        }