[백준]22234: 💰가희와 은행 - JAVA

[백준]22234: 💰가희와 은행

 

22234번: 가희와 은행

풀이

🪑 Queue, PriorityQueue를 활용하는 자료구조 문제이다. 이와 같은 유형은 자주 접해본 유형이었다!

 

📝 문제가 길어서 어려워 보이지만, 그렇지 않다. 차근차근 정리해 보자!

• 은행은 창구가 하나이다. 즉, 한 번에 손님 한명만 처리할 수 있다.
• W - 1초가 지날때 까지 창구에 있는 직원이 처리하는 고객을 출력하면 된다.
• 손님은 id, 소요 시간, 들어온 시간에 대한 정보를 가지고 있다.
• 라운드 로빈 방식으로 업무를 처리한다.

 

🙋‍♀️ 이 문제에서 유의할 점은 업무 처리에 대한 로직 순서이다! 순서가 잘못된다면 런타임에러를 만나게 될 것이다!

 

 

🔧 문제를 풀어보쟈아아아!

1. 영업 시작과 동시에 존재하는 손님들의 정보는 Queue로 관리하며 업무 처리 로직을 수행하는 손님도 Queue에 담긴 순서대로 진행한다.
2. 추가로 들어오는 손님 정보는 PriorityQueue로 관리하며 들어온 시간 순서대로 정렬한다.
3. 라운드 로빈 방식으로 업무를 진행하며, Queue에 맨 앞에있는 손님에 대한 업무를 먼저 처리한다. 그 다음에 PriorityQueue를 확인하며 새로 들어오는 손님을 Queue에 차례대로 담아주고(새로 들어오는 손님 먼저 Queue에 담아준다!) 현재 손님의 업무가 끝나면 업무 시간에 따라 Queue에 마지막에 담을지 안담을지 결정하면 된다.

 

 

🔹 영업 시작과 동시에 존재하는 손님들의 정보는 Queue로 관리한다.

- 입력 순서대로 Queue에 담아준다.

 

🔹 추가로 들어오는 손님 정보는 PriorityQueue로 관리하며 들어온 시간 순서대로 정렬한다.

- 입력 시간대로 내림차순 정렬하는 PriorityQueue를 만들어 순서대로 담아준다. 

 

🔹 라운드 로빈 방식으로 업무를 진행하며, Queue에 맨 앞에있는 손님에 대한 업무를 먼저 처리한다. (순서 중요!)

1. Queue에 맨 앞에 있는 손님의 정보를 꺼낸다.
2. 손님의 업무 수행 시간이 T보다 크면 T시간 동안 업무를 진행하고, T보다 작거나 같으면 손님의 업무 수행 시간 만큼만 업무를 진행한다.
3. PriorityQueue의 첫 번째 값과 현재 시간을 비교하여 현재 시간보다 작거나 같은 시간이라면 해당 손님이 은행에 도착했다 라는 의미이므로 PriorityQueue에서 꺼내 Queue에 담아준다. 이 작업은 첫 번째 값이 현재 시간보다 작거나 같은 동안 반복된다. 
4. 현재 손님의 업무를 처리하고 아직 업무 처리 시간이 남았다면(손님의 업무 수행 시간이 T보다 크다면) 손님의 업무 시간에서 T시간을 빼 주고 다시 Queue에 담아 맨 마지막으로 보내준다.
5. W시간이 되기 전까지 위의 작업을 반복한다.

 

 

코드

//22234: 가희와 은행
import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n, t, w, m;
    static Queue<Customer> q = new LinkedList<>();
    static PriorityQueue<Customer> customer_list;
 
    public static void main(String[] args) throws IOException {
 
        //입력
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        String str = bf.readLine();
        StringTokenizer st = new StringTokenizer(str);
        n = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());
 
        for(int i = 0; i < n; i++) {
            str = bf.readLine();
            st = new StringTokenizer(str);
            int num = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());
            q.offer(new Customer(num, time, 0));
        }
 
        m = Integer.parseInt(bf.readLine());
        customer_list = new PriorityQueue<>((o1, o2) -> o1.input_time - o2.input_time);
        for(int i = 0; i < m; i++) {
            str = bf.readLine();
            st = new StringTokenizer(str);
            int num = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());
            int input_time = Integer.parseInt(st.nextToken());
            customer_list.offer(new Customer(num, time, input_time));
        }
        //입력 끝
        System.out.print(round_robin().toString());
    }
 
    public static StringBuilder round_robin() {
        StringBuilder sb = new StringBuilder();
        int current_time = 0;
        while(current_time < w) {
            Customer current = q.poll();
 
            if(current.time > t) {
                for(int i = 0; i < t; i++) {
                    if(current_time >= w) return sb;
                    sb.append(current.num + "\n");
                    current_time++;
                }
            } else {
                for(int i = 0; i < current.time; i++) {
                    if(current_time >= w) return sb;
                    sb.append(current.num + "\n");
                    current_time++;
                }
            }
 
            while(!customer_list.isEmpty() && customer_list.peek().input_time <= current_time) {
                q.offer(customer_list.poll());
            }
 
            if(current.time > t) {
                current.time -= t;
                q.offer(current);
            }
        }
        return sb;
    }
 
    public static class Customer {
        int num, time, input_time;
 
        public Customer(int num, int time, int input_time) {
            this.num = num;
            this.time = time;
            this.input_time = input_time;
        }
    }
}