백준 21773 - 가희와 프로세스 1

문제

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

리뷰

우선순위큐를 활용해 풀이할 수 있는 간단한 문제였다.

프로세스를 표현하기 위해 id, time, priority 필드를 가진 Process
클래스를 정의하고, 문제에서 주어진 실행시킬 프로세스를 선택하는 기준을 우선순위큐에
Comparator를 통하여 구현하였다.

주어진 스케줄러의 알고리즘에서 실행되는 프로세스외 나머지 프로세스들의 우선 순위를
높이는 연산은, 실행되는 프로세스의 우선순위를 하나 낮춰줌으로써 $O(N)$의
시간 복잡도를 띄지 않게 구현할 수 있다.

또한, 실행 시간이 남았을 경우에만 힙에 프로세스를 다시 투입하도록 코드를 구성해
실행 시간이 남은 프로세스가 있는지 확인하는 과정을 실현할 수 있게 하였다.

로직의 시간복잡도는 프로세스를 처리하는 부분에서 $O(Tlogn)$으로 수렴하고
이는 $T=10^6$, $n=10^5$인 최악의 경우에도 무난히 제한 조건 1초를 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

import static java.lang.Integer.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = parseInt(st.nextToken());
        int n = parseInt(st.nextToken());
        PriorityQueue<Process> pq = new PriorityQueue<>((p1, p2) -> {
            if (p1.priority == p2.priority) return compare(p1.id, p2.id);

            return compare(p2.priority, p1.priority);
        });

        int id, priority, time;
        while (n-- > 0) {
            st = new StringTokenizer(br.readLine());
            id = parseInt(st.nextToken());
            time = parseInt(st.nextToken());
            priority = parseInt(st.nextToken());

            pq.offer(new Process(id, time, priority));
        }


        StringBuilder sb = new StringBuilder();
        while (T-- > 0 && !pq.isEmpty()) {
            Process process = pq.poll();

            sb.append(process.id).append("\n");
            process.priority--;
            process.time = Math.max(process.time - 1, 0);
            if (process.time == 0) continue;
            pq.offer(process);
        }

        System.out.print(sb);
        br.close();
    }

    static class Process {
        int id, time, priority;

        public Process(int id, int time, int priority) {
            this.id = id;
            this.time = time;
            this.priority = priority;
        }
    }
}

결과