[Baekjoon] 21773_가희와 프로세스 1

Gold V

문제(출처: https://www.acmicpc.net/problem/21773)

---

< 가희와 프로세스 1>

 

문제 풀이 

 

우선순위 큐를 사용해서 문제를 해결했다.

 

우선순위 값이 제일 큰 프로세스 중 id 가 가장 작은 프로세스를 골라줍니다. 1초가 지난 후 이 프로세스를 제외한 나머지 프로세스들의 우선순위가 1 상승한다고 했지만 나머지를 다 1 상승시키기에는 시간이 오래 걸려 반대로 골라준 프로세스의 우선순위를 1 줄여줍니다. 프로세스의 실행 시간도 1 줄인 후 시간이 0이 아니라면 다시 우선순위 큐에 추가해 줍니다.

 

 my solution (Java)

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

public class _21773_ { // 가희와 프로세스 1

	public static class Process implements Comparable<Process> {
		int id;
		int time;
		int level;

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

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

	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int t = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());

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

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			queue.add(new Process(a, b, c));
		}

		for (int i = 0; i < t; i++) {
			if (queue.isEmpty())
				break;
			Process process = queue.poll();
			bw.write(process.id + "\n");

			process.time -= 1;

			if (process.time > 0) {
				process.level -= 1;
				queue.add(process);
			}
		}
		bw.flush();
	}
}

 

Main

변수)
Process : id, 시간(time), 우선순위(level) / 정렬 : 우선순위 내림차순 > id 오름차순
t : t 초
n : 프로세스 개수
queue : Process 순으로 정렬하는 우선순위 큐
a : id
b : 실행을 마치는데 필요한 시간
c : 초기 우선순위

 

- 시간(t)과 프로세스 개수(n) 입력

- 프로세스의 id(a), 실행을 마치는데 필요한 시간(b), 초기 우선순위(c)를 입력받아 qeuue에 저장

- t초만큼 반복

: 실행 시간이 남은 프로세스가 없다면 종료

: queue에서 우선순위 값이 제일 크고 id가 가장 작은 프로세스 뽑기

: 프로세스 시간을 1초 줄인 후 아직 시간이 남았다면 우선순위를 1 줄인 후 queue에 저장

- 답 출력

---

---