PCCP 모의고사 2회 - 카페 확장

1. 문제 정의

2. 문제 접근

시간대 별로 사람이 몇명이 들어오는지를 계산해주면 될 것 같다. 시간 범위는 마지막 사람이 들어올 때를 마지막으로 더 이상 계산해 주지 않아도 된다. 그때가 들어오는 사람이 최대가 되는 시점이기 때문이다.

3. 문제 풀이

1. 마지막 사람이 들어오는 시점에 시간을 최대 시간으로 정의한다.

2. 최대 시간 만큼 사람수를 계산하는 배열을 정의한다.

3. 소요되는 시간을 정의한다.

4. for 문을 돌면서 order가 들어올 때 마다 people 배열을 갱신한다.

4. 정답을 return 해 준다.

4. 코드

// 누적합 원리 이용

import java.util.*;

class Solution {
    public int solution(int[] menu, int[] order, int k) {
        int answer = 0;
        int length = (order.length-1)*k+1;
        int[] people = new int[length];
        int takes_time = 0;
        for(int o = 0; o < order.length; o++) {
            takes_time = Math.max(takes_time, o*k) + menu[order[o]];
            for(int i = o*k; i < takes_time && i < length; i++) people[i]++;
        }
        
        for(int p: people) answer = Math.max(answer, p);
        
        return answer;
    }
}

 

// 큐 사용해서

import java.util.*;

class Solution {
    public int solution(int[] menu, int[] order, int k) {
        int answer = 0;
        // 작업 중인 애들 들어가는 곳(order_index)
        Queue<Integer> serve = new LinkedList<>();
        // order_index, making_time
        Map<Integer, Integer> map = new HashMap<>();
        // 0초부터 흐르는 시간
        int takes_time = 0;
        // 만드는 시간
        int making_time = 0;
        // 마지막 손님 오는 시간
        int last_time = order.length * k + 1;

        for (int o = 0; o < last_time && o < order.length; o++) {
            // 만드는 대기열에 넣기

            making_time += menu[order[o]];
            map.put(o, making_time);
            serve.add(o);

            // k초만큼 시간 지나감
            for (int t = 0; t < k; t++) {
                takes_time++;
            }
            
            if(map.get(serve.peek()) == null) {
                    making_time = takes_time;
            }

            if(map.get(serve.peek()) != null && map.get(serve.peek()) <= takes_time) {
                answer = Math.max(answer, serve.size());
                serve.poll();
            }
            
           answer = Math.max(answer, serve.size()); 
        } 
        
        return answer;
    }
}

 

 

5. 회고

누적합 문제와 비슷한 유형인 것 같다.