[백준 22234] 가희와 은행 (Java)

문제 링크: https://www.acmicpc.net/problem/22234

22234번: 가희와 은행

1. 주의할 점

- RR(RoundRobin) 문제다

- 스케줄링 문제의 경우, 각 작업이 일어나는 순서와 정렬 방식에 주의한다

 

2. 구현

- 대기큐 Q에는 0초에 대기중인 고객들에 대한 정보를 저장한다

- 1초 이후에 들어오는 고객들은 입장 시간에 대한 오름차순으로 정렬되어 있지 않기 때문에 우선순위 큐 PQ를 통해 정렬을 한다

- 현재 시간(curTime)을 0초로 설정하고 다음 순서대로 While문 내부를 수행한다

- 대기큐에서 고객의 업무를 처리한다. 이때, 고객의 업무가 끝나는 시간보다 한 고객당 할당할 수 있는 시간 T와 비교하여 더 작은 값을 기준으로 처리한다(Time Quantum)

- 위의 값 중에서 작은 값을 골랐을 때, 현재 시간+작은 값이 은행 업무 종료시간 finTime과 비교하여 작은값 동안 Li 리스트에 처리하는 고객 번호를 추가한다

- 현재 시간+작은 값이 은행 업무 종료시간 finTime을 넘어가는 경우, While문을 종료핟나

- 우선순위큐에서 대기중인 고객들 중, 대기큐에 올 수 있는 고객이 있는 경우 추가한다

- While문의 시작부분에서 처리중이였던 고객의 업무가 남아있다면, 대기큐에 시간을 차감하고 추가한다

- Join 함수를 통해 Li 리스트에 추가했던 고객번호를 줄 단위로 구분하여 출력한다

 

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    static class Info implements Comparable<Info> {
        int idx,needTime,arriveTime;
        public Info(int idx, int needTime, int arriveTime){
            this.idx=idx;
            this.needTime=needTime;
            this.arriveTime=arriveTime;
        }
        @Override
        public int compareTo(Info o){
            return Integer.compare(this.arriveTime,o.arriveTime);
        }
    };
    
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    int num = Integer.parseInt(st.nextToken());
	    int t = Integer.parseInt(st.nextToken());
	    int finTime = Integer.parseInt(st.nextToken());
	    Queue<Info> q = new LinkedList<>();
	    
	    for(int i=0;i<num;i++){
	        st = new StringTokenizer(br.readLine());
	        int idx = Integer.parseInt(st.nextToken());
	        int timeLeft = Integer.parseInt(st.nextToken());
	        q.offer(new Info(idx,timeLeft,0));
	    }
	    int afterOneMin = Integer.parseInt(br.readLine());
	    PriorityQueue<Info> pq = new PriorityQueue<>();
	    
	    for(int i=0;i<afterOneMin;i++){
	        st = new StringTokenizer(br.readLine());
	        int idx = Integer.parseInt(st.nextToken());
	        int timeLeft = Integer.parseInt(st.nextToken());
	        int arriveTime = Integer.parseInt(st.nextToken());
	        pq.offer(new Info(idx,timeLeft,arriveTime));
	    }
	    int curTime = 0;
	    List<String> li = new ArrayList<>();
	    
	    while(!q.isEmpty()){
	        //q에서 원소 하나 빼고 실행
	        Info ii = q.poll();
	        if(ii.needTime<=t){
	            for(int i=curTime;i<Math.min(curTime+ii.needTime,finTime);i++)
	                li.add(String.valueOf(ii.idx));
	            curTime+=ii.needTime;
	        }
	        else{
	            for(int i=curTime;i<Math.min(curTime+t,finTime);i++)
	                li.add(String.valueOf(ii.idx));
	            curTime+=t;
	        }
	        if(curTime>finTime) break;
	        //pq에서 추가될 요소 있는지 확인
	        while(!pq.isEmpty()){
	            int arriveTime = pq.peek().arriveTime;
	            if(arriveTime<=curTime){
	                Info ii2 = pq.poll();
	                q.offer(new Info(ii2.idx, ii2.needTime, ii2.arriveTime));
	            }
	            else break;
	        }
	        //q에서 뺐던 원소가 다시 추가된다면 추가
	        if(ii.needTime>t) q.offer(new Info(ii.idx,ii.needTime-t,ii.arriveTime));
	    }
	    final String answer = String.join("\n",li);
	    System.out.println(answer);
	}
}