[백준] 가희와 은행 22234 (라운드로빈)

https://www.acmicpc.net/problem/22234

💡문제 분석 요약

• 상황
  • 은행원이 있고 은행 업무를 처리하기 위한 사람들이 여러 명있다.
  • 들어온 순서대로 처리하며 이때, 다 업무를 처리하지 못한다면 다시 줄을 서야한다.
• 출력
  • 0~W-1초 동안에 각 초에 어떤 사람의 업무를 보고 있었는지 id를 출력한다.

이 문제는 매우 좋은 문제인 것 같다. 왜냐하면 OS에 나오는 CPU 스케줄링 방식 중 라운드로빈 방식과 매우 유사하며 이를 구현하기 위한 로직을 생각해보는 문제이기 때문이다.

모든 사람들에게 업무를 처리할 수 있는 일정한 시간이 똑같이 주어지고 그 시간 안에 해야하는 업무들을 다 끝내지 못한다면 다시 큐에 들어간다는 점이 “라운드로빈”과 유사하다.

 

---

참고) CPU 스케줄링이란?

프로세스들은 CPU를 할당 받아야 한다. 이때, CPU를 할당할 프로세스를 선정하는 것이 CPU 스케줄링이다.

• CPU 선점 방식과 비선점 방식
  • CPU를 프로세스에 할당할 때 실행중이었던 프로세스(혹은 스레드)를 어떻게 할 것인지에 따라 선점과 비선점으로 나뉜다.
  • 선점 방식은 실행중이었던 프로세스(혹은 스레드)를 “강제로” 종료하고 다른 프로세스를 실행하는 것이다.
  • 비선점 방식은 실행중이었던 프로세스(혹은 스레드)가 작업을 다 완료할 때까지 기다린 후 다른 프로세스를 실행하는 것이다.
• 선점 방식 알고리즘 종류
  • 1. Round Robin (RR)
    • 우선순위를 두지 않고 “순서대로” 시간 단위로 CPU를 할당한다.
    • 프로세스(혹은 스레드)가 할당받은 CPU 사용 시간이 지나면 하던 일을 멈추고 ReadyQueue에 들어가 다시 CPU를 기다린다.

💡알고리즘 설계

• N, T, W, M는 구간 [1, 2×105]에 속하는 정수
• 자료구조
  • 실제 업무를 위한 대기줄과 은행 입장 시간에 따른 생긴 줄 2가지가 있다.
    • 이때, 실제 업무를 위한 대기줄은 줄을 선 순서대로이므로 큐로 관리하면 된다. (Deque)
    • 그리고 은행 입장 시간에 따른 생긴 줄은 입장 시간을 기준으로 오름차순을 유지하는 우선순의 큐로 관리하면 된다. (PriorityQueue)
• 1초씩 증가하면서 각 상황에 맞게 작업을 수행하는 반복문
  • 1. PriorityQueue에서 은행 입장 시간이 되면 꺼내서 실제 업무보는 대기줄에 넣기
  • 1. 작업을 수행하기
    • 이때, 주어진 시간 내에 작업을 다 끝내지 못했다면 대기 줄 끝으로 보낸다.
    • 작업을 다 끝냈다면 제거한다.

💡코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.*;

public class 가희와은행 {
    public static void main(String[] args) throws Exception{
        new 가희와은행().solution();
    }

    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        PriorityQueue<Node> pq = new PriorityQueue<>(); // 은행 오픈 후 들어오는 사람의 정보
        Deque<Node> preWait = new ArrayDeque<>(); // 은행에서 실제 대기줄

        int N = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());

        for(int i = 0 ; i < N; i++){
            st = new StringTokenizer(br.readLine());
            int id = Integer.parseInt(st.nextToken()); // 고객
            int wasteTime = Integer.parseInt(st.nextToken()); // 필요 시간
            preWait.offer(new Node(id, wasteTime, 0)); // 영업 시간 전에 들어온 손님
        }

        int M = Integer.parseInt(br.readLine());

        for(int i = 0 ; i< M; i++){
            st = new StringTokenizer(br.readLine());
            int id = Integer.parseInt(st.nextToken());
            int wasteTime =Integer.parseInt(st.nextToken());
            int enter = Integer.parseInt(st.nextToken());
            pq.offer(new Node(id, wasteTime, enter)); // 영업 시간 이후 들어온 손님
        }

        StringBuilder sb  = new StringBuilder();
        int time = 0;

        int job = 0;

        while(time < W){ // 1초씩 증가하면서 조건에 따라 큐에 넣거나 꺼내거나 작업을 한다.
            Node cur = preWait.peek(); // 기다리는 줄에서 먼저 온 한 명을 확인한다.

            // 은행에 들어오는 사람 관리
            if(!pq.isEmpty() && pq.peek().enter == time){ // 만약 지금 타임이 입장한 사람이 있으면 실제 줄에 옮겨준다.
                preWait.offer(pq.poll());
            }

            // 사람 교체 작업
            if(cur.wasteTime - job == 0){ //지금 사람이 할 일이 끝났다면
                preWait.poll(); // 대기 줄에서 꺼낸다.
                job = 0; // 작업 초기화
            }else if(job >= T){ // 작업이 끝나지 않았지만 남아있다면
                preWait.poll(); // 대기 줄에서 꺼낸다.
                preWait.add(new Node(cur.id, cur.wasteTime - job, 0)); // 맨 뒤로 보낸다.
                job = 0; // 작업 초기화
            }

            //실제 일하는 부분
            sb.append(preWait.peek().id).append("\\n"); // 현재 작업하는 사람의 id를 출력
            time++; // 시간 증가
            job++; // 작업 수 증가

        }
        System.out.println(sb);

    }

    public class Node implements Comparable<Node>{
        int id;
        int wasteTime;
        int enter;

        public Node(int id, int wasteTime, int enter){
            this.id = id;
            this.wasteTime = wasteTime;
            this.enter = enter;
        }
        @Override
        public int compareTo(Node node){
            return this.enter - node.enter;
        }
    }

}

💡시간복잡도

• que에 넣기
  • → M명을 넣기 때문에 O(M)
• pq에 고객을 삽입/삭제하는데 O(log N) 시간이 소요
  • → N명을 넣기 때문에 O(N logN)
• W만큼 반복문 돌아감
  • 이때 큐에서 넣고 빼는 것은 O(1)이므로 O(W) 소요