문제

주원이는 카페를 운영하고 있습니다. 주원이의 카페는 맛집으로 소문나서 항상 줄이 끊이지 않습니다. 하지만 카페가 협소하여 커피를 기다리는 손님들은 종종 불만을 토로하고 있습니다. 주원이는 카페를 확장하기로 하고, 얼마나 많은 손님들이 동시에 카페에 머무는지 확인해보려 합니다.

주원이네 카페에는 영업을 시작하자마자 0초에 손님 한 명이 가게에 도착하고, 정확히 k초마다 새로운 손님 한 명이 카페에 와서 줄을 섭니다. 손님들은 키오스크를 통해 주문하고, 주원이는 주문받은 순서대로 음료를 만듭니다. 주원이는 음료를 한 번에 하나씩 만들며, 지금 만들고 있는 음료를 다 만들면 다음 음료를 만들기 시작합니다. 손님은 자신이 주문한 음료를 받자마자 카페를 나갑니다. 주원이네 카페에는 여러 종류의 음료를 판매하고 있는데 각 음료들은 0번부터 차례대로 번호가 지정되어 있습니다. 또한 주원이가 같은 종류의 음료를 만드는데 걸리는 시간은 항상 동일합니다.

주원이는 오늘 주문받은 음료 목록을 이용하여, 카페에서 손님들이 동시에 최대 몇 명이 머물렀는지 알고 싶습니다. 손님들이 카페에 도착하여 주문하기까지 걸린 시간과 음료를 받은 후 카페를 나가는 시간은 음료 제조 시간에 비해 대단히 짧기 때문에 무시합니다. 한 손님이 카페에서 나감과 동시에 다른 손님이 카페에 들어올 경우, 나가는 손님이 먼저 퇴장한 다음 들어오는 손님이 입장합니다.

예를 들어, 주원이네 카페에서 세 종류의 음료를 판매하고 제조 시간은 0번 음료가 5초, 1번 음료가 12초, 2번 음료는 30초 소요된다고 가정합니다. 영업을 시작한 뒤 4명의 손님이 각각 0초, 10초, 20초, 30초에 카페에 도착하여 순서대로 1번, 2번, 0번, 1번 음료를 주문한 경우, 영업 시작 후 30초부터 42초 사이에 3명의 손님이 기다리게 되고, 이때가 동시에 기다리고 있는 손님이 가장 많은 시간입니다.

주원이네 카페에서 판매하는 각 음료들의 제조 시간을 담은 정수 배열 menu와 오늘 손님들이 주문한 음료가 순서대로 적힌 배열 order, 새로운 한 명의 손님이 방문하는데 걸리는 시간인 k가 매개변수로 주어집니다. 오늘 카페에 동시에 존재한 손님 수의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한 사항

1 ≤ menu의 길이 ≤ 100

• menu[i]는 i번 음료의 제조 시간을 의미합니다.
• 1 ≤ menu의 원소 ≤ 100
  1 ≤ order의 길이 ≤ 10,000
• order[i]는 i번째 손님이 주문한 음료의 번호입니다.
• 0 ≤ order의 원소 < menu의 길이
  1 ≤ k ≤ 100

입력

menu : [5, 12, 30]
order : [1, 2, 0, 1]
k : 10

출력

3

내가 했던 풀이

1. time을 1씩 증가시키면서 해당 시간에 대한 처리들을 진행한다.
2. ready(queue)에는 [wating, making]이 들어가게 되는데 wating은 해당 손님의 음료 제조 시작 시간을 의미하고 making은 음료를 제조하는 데 들어가는 시간이다. 만약 시간시간+제조시간이 time과 동일하다면 음료가 만들어졌으므로 ready에서 제거한다.
3. index는 n번째 손님을 의미하며 손님이 ready에 들어갈 때마다 1씩 증가한다. 그러므로 index*k는 다음 손님이 들어오는 시간이 된다. 이를 next라고 할 때 time과 일치할 경우, 새로운 손님을 ready에 넣어준다. 이 때, 해당 손님의 wating 시간은 손님 앞에 다른 손님이 있을 경우 다른 손님들의 음료가 모두 처리되는 시간 이후부터 일 것이다. 이를 판단하기 위해 앞 선 손님들의 making 시간을 더해준다. 해당 값이 0일 경우에는 앞 손님이 없는 것이므로 time(현재시간)을 넣어주고, 0 이상일 경우에는 모두 합한 making 시간과 제일 앞 손님의 음료가 만들어지기 시간하는 시간을 더해준다. 즉, wating은 ready에 들어갈 손님의 음료가 제조되기 시작하는 시간이 된다. 이를 ready에 넣어주고 index를 증가시켜준다.
4. ready.length와 answer 값 중 더 큰 값을 찾아주면서 index가 order.length와 같아질 때까지 반복한다.

코드

function solution(menu, order, k) {
    var answer = 0;
    let time = 0;
    let ready = [];
    let index = 0;

    while(index<order.length) {
        if(ready.length && ready[0][0]+ready[0][1]===time) {
            ready.shift();
        }

        let next = index*k;
        if(next===time) {
            let wating = 0;

            for(let i=0; i<ready.length; i++) {
                wating += ready[i][1];
            }

            wating = wating === 0 ? time : wating + ready[0][0];
            ready.push([wating, menu[order[index]]]);
            index++;
        }

        answer = Math.max(ready.length, answer);
        time++;
    }
    return answer;
}

회고

50% 정답만 맞췄던 문제. 큐로 접근하는 것까지도 생각했는데 너무 어렵게 접근한 것 같다. time을 1부터 쭉 증가시켜주는 방향으로 생각하긴 했는데 시간 효율성을 생각하다가 order를 반복해주는 걸로 복잡하게 구현했다. 다른 풀이를 참고했는데 이해되기까지 조금 어려웠다. waiting이라는 시간이 다들 대기시간으로 표현을 해서 해당 손님이 대기하는 시간이라고 판단을 해서 어떻게 이런 결과가 나오는거지? 의아했지만, 제대로 보니 해당 손님의 음식이 만들어지기 시작하는 시간이라고 판단하는 게 맞았다. 이 부분이 해소되니까 뒷 부분은 금방 이해가 됐다. 풀 수 있었던 문제여서 아쉽지만... 그래도 50%는 맞았으니까... 다음엔 풀 수 있겠지