[프로그래머스/LV2] [PCCP 모의고사 #2] 3번 - 카페 확장 (Java)

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

🙋‍♂️ 들어가며

우선 조건을 정리해보자

- 0초에 손님 도착, k초마다 손님 입장
- 주문받은 순서대로 음료 만든다
- 음료를 한번에 1개씩 만들고, 지금 만들고 있던 음료를 다 만들면 다음 음료 만들기 시작
- 음료 받으면 나간다

*구할 것 -> 동시에 최대 몇명 머물렀는지 알고 싶다

• 1 <= menu <= 100
• 1 <= order <= 10000
• 1 <= k <= 100

생각을 한번 해보자

손님이 일찍 도착해도, 기계를 사용 못하면 기다려야하는 것

우선 조건은 N <= 10000 이라 $O(N^2)$ 도 가능하겠다

testcase로 보자

# tc-1
visit_time = {0, 10, 20, 30};
waiting_time = {12, 42, 47, 59};


# tc-2
visit_time = {0, 5, 10, 15, 20};
waiting_time = {5, 10, 15, 20, 25};

그렇다면 order = 10, k = 100이면?

visit_time = {0, 100, 200, 300};
waiting_time = {10, 20, 30};

-> final_waiting_time = {10, 110, 210, 310};

아 그러면 손님 방문시간과 음료 만드는 대기시간을 비교하여 더 오래걸리는 것을 쓰고 + 현재 손님에게 필요한 메뉴 추가 해주면 되겠다

그래서 첫 값을 대입하고 이런식으로 시간배열을 비교하면서 만들 수 있지 않을까?

구조 설계

1. 첫값 대입
2. 대기시간 = (손님 오는 시간 vs 이전 손님 대기시간) + 음료 만드는 시간

✅ 정답 코드

class Solution {
    public int solution(int[] menu, int[] order, int k) {
        int max_people = 0;
        
        // 1. 첫 값 대입
        int N = order.length;
        int[] waiting_time = new int[N];
        int first_idx = order[0];
        int first_menu = menu[first_idx];
        waiting_time[0] = first_menu;
        
        // 2. 대기시간
        // (손님오는 시간 vs 이전 손님 대기시간) + 음료 만드는 시간
        for (int i = 1; i < N; i++) {
            int visit_time = i*k;
            int prev_customer_waiting = waiting_time[i-1];
            int cur_menu = menu[order[i]];
            waiting_time[i] = Math.max(visit_time, prev_customer_waiting) + cur_menu;
        }
        
        // 3. 계산
        for (int i = 0; i < N; i++) {
            int waiting = 0;
            int cur_time = i * k;
            for (int j = 0; j < i+1; j++) {
                // 3-1. 만약 현재시간보다 음료 만드는 시간이 더 길면
                if (cur_time < waiting_time[j]) {
                    waiting++;
                }
            }
            
            // 3-2. 갱신
            max_people = Math.max(waiting, max_people);
        }
        
        return max_people;
    }
}