21773번(가희와 프로세스1)

첫 시도

• 시간복잡도를 계산하지 않고 완전탐색으로 시도
• 우선순위가 가장 높은 프로세스를 실행하고 나머지 프로세스들의 값 변경
• Collections.sort로 우선순위에 맞게 정렬
• 시간복잡도가 T * n = 10^11이므로 시간초과

해결

• 우선순위 큐 사용
• java에서 우선순위 큐를 사용해보지 않아 이번기회에 공부

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

public class Main {

    public static void main(String[] ars) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        PriorityQueue<Process> q = new PriorityQueue<>();

        for(int i = 0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            int id = Integer.parseInt(st.nextToken());
            int sec = Integer.parseInt(st.nextToken());
            int prio = Integer.parseInt(st.nextToken());

            q.offer(new Process(id, sec, prio));
        }

        for(int i = 0; i<T; i++){
            if (q.isEmpty()) { //  프로세스가 없을 시 종료
                break;
            }

            Process ps = q.poll();
            sb.append(ps.id+"\n");

            if(ps.sec == 1){ // 남은 시간이 1초면 continue, 큐에 다시 넣을 필요 없음
                continue;
            }
            // 현재 프로세스의 prio를 감소시키면 다른 프로세스의 prio를 증가시키는 것과 동일, n번 반복할 필요 x
            q.offer(new Process(ps.id, ps.sec - 1, ps.prio - 1));
        }
        System.out.println(sb.toString());

    }
}
class Process implements Comparable<Process>{
    int id;
    int sec;
    int prio;

    Process(int id, int sec, int prio){
        this.id = id;
        this.sec = sec;
        this.prio = prio;
    }

    @Override
    public int compareTo(Process o) {
        if(this.prio == o.prio){
            return this.id - o.id;
        }
        return o.prio - this.prio;
    }
}

참고

• https://gre-eny.tistory.com/289