개요
- 하드 디스크는 한 번에 하나의 작업만 수행할 수 있다.
- 우선순위 디스크 컨트롤러를 구현해야한다.
- 어떤 작업 요청이 들어왔을 때, 작업의 번호, 작업의 요청 시각, 작업의 소요 시간을 저장해 두는 대기 큐가 존재.
- 이 큐는 처음에는 비어있다.
- 디스크 컨트롤러는 하드디스크가 쉬고 있고, 대기 큐에 작업이 있을경우 우선순위가 높은 작업을 디스크에게 수행시킨다.
- 우선순위가 높은 것: 작업의 소요시간이 짧은 것, 작업의 요청 시각이 빠른 것, 작업의 번호가 작은 것
- 하드디스크는 작업을 한 번 시작하면 작업을 마칠 때까지 그 작업만 수행한다.
- 하드디스크는 작업을 마치자마자 바로 다음 작업 수행이 가능하다.
- 각 작업에 대한 반환 시간: 작업 요청부터 종료까지 걸린 시간
<조건>
- 알 수 없음
<입력>
- 작업의 정보가 담겨있는 int[][] jobs
- jobs의 길이: 1 ~ 500
- jobs[i]: [작업이 요청되는 시점, 작업의 소요시간]
- 작업이 요청되는 시점: 0 ~ 1,000
- 작업의 소요시간: 1 ~ 1,000
<반환>
- 모든 요청 작업의 반환 시간의 평균을 반환하라.
문제 풀이
먼저 내가 시도한 풀이는
대기 큐를 구현한 우선순위 큐와 작업을 요청 시각으로 정렬한 List를 사용한 방법이다.
알고리즘은 다음과 같다.
- 대기 큐를 우선순위 큐로 구현한다.
- 작업을 요청 시간 순으로 정렬해서 넣는다.
- 요청 시각이 같은 작업들을 대기 큐에 넣는다.
- while문으로 반복한다.
- 대기 큐에서 작업을 꺼낸 후 반환 시간을 계산해 넣는다.
- 작업 종료 시간까지의 작업들을 대기 큐에 집어넣는다.
- 작업 종료에 따라 현재 시간을 갱신한다.
- 대기 큐가 비어있는데, 작업이 남아 있으면 대기 큐에 작업을 넣는다.
- 대기 큐와 작업이 모두 비어있을 경우 while문을 종료한다.
- 반환 시간의 평균을 계산해 return한다.
차근차근 하나씩 살펴보자.
1. 대기 큐를 우선순위 큐로 구현한다.
먼저 Job이라는 클래스를 하나 선언해서 작업의 번호, 요청 시각, 소요 시각등을 관리했다.
이때 Comparable 인터페이스를 구현하고, compareTo 메서드를 오버라이드 하여 우선순위 큐의 정렬 방식을 지정했다.
//1. 대기 큐를 우선순위 큐로 생성
PriorityQueue<Job> pq = new PriorityQueue<>();
...
class Job implements Comparable<Job>{
private int num;
private int startTime;
private int cost;
public Job(int num, int startTime, int cost){
this.num = num;
this.startTime = startTime;
this.cost = cost;
}
public int getNum(){
return this.num;
}
public int getStartTime(){
return this.startTime;
}
public int getCost(){
return this.cost;
}
@Override
public int compareTo(Job job){
if(this.cost > job.getCost()) return 1;
else if(this.cost < job.getCost()) return -1;
else{
if(this.startTime > job.getStartTime()) return 1;
else if(this.startTime < job.getStartTime()) return -1;
else{
if(this.num > job.getNum()) return 1;
else return -1;
}
}
}
}
2. 작업을 요청 시간 순으로 정렬해서 넣는다.
작업들은 요청 시간순으로 정렬되어서 있지 않다.
그렇기에 우리는 요청 시간순으로 정렬할 필요가 있다.
나는 Collection.sort()를 사용하기 위해
Comparator를 하나 구현해주었다.
//2. 작업을 요청 시간 순으로 정렬
List<Job> list = new ArrayList<>();
for(int i = 0; i < jobs.length; i++){
list.add(new Job(i, jobs[i][0], jobs[i][1]));
}
Collections.sort(list, new JobStartTimeComparator());
...
class JobStartTimeComparator implements Comparator<Job>{
@Override
public int compare(Job j1, Job j2){
if(j1.startTime > j2.startTime) return 1;
else if(j1.startTime < j2.startTime) return -1;
else return 0;
}
}
3. 요청 시간이 같은 작업들을 모두 대기 큐에 넣기.
이때 curTime이라는 변수를 선언하고, returnTime이라는 List또한 생성하였는데
각각, curTime은 시간을 관리하는 변수이며, returnTime은 반환 시간을 넣을 List이다.
//3. 요청 시간이 같은 작업들을 while문으로 돌려서 대기 큐에 넣기.
int curTime = list.get(0).getStartTime();
while(!list.isEmpty() && curTime == list.get(0).getStartTime()){
pq.add(list.remove(0));
}
List<Integer> returnTime = new ArrayList<>();
4 . while문 반복
//4. while문 반복
while(true){
5. 대기 큐에서 작업 꺼낸 후 반환 시간 계산해서 넣기
//5. 대기 큐에서 작업 꺼낸 후 반환 시간 계산 해 넣기
Job job = pq.poll();
int startTime = job.getStartTime();
int endTime = curTime + job.getCost();
returnTime.add(endTime - startTime);
6. 작업 종료 시간까지의 작업들을 대기 큐로 넣기
//6. 작업 종료 시간까지의 작업들을 while문 돌려서 대기 큐에 넣기.
while(!list.isEmpty() && list.get(0).getStartTime() <= job.getCost() + curTime){
pq.add(list.remove(0));
}
7. 작업 종료에 따른 현재 시간 갱신
//7. 작업 종료에 따른 시간 갱신
curTime += job.getCost();
8. 대기 큐가 비어있는데, 작업이 남아있을 때, 대기 큐에 작업 넣기 + 현재 시간 갱신
if(pq.size() == 0 && !list.isEmpty()){
pq.add(list.remove(0));
curTime = pq.peek().getStartTime();
}
9. 대기 큐가 비어있는데, 작업도 없을 때 while문 탈출
if(pq.size() == 0) break;
10. 반환 시간 계산
//10. 반환 시간 List로 답 계산
int sum = 0;
for(int i = 0; i < returnTime.size(); i++){
sum += returnTime.get(i);
}
return sum / returnTime.size();
전체 코드
import java.util.*;
class Solution {
public int solution(int[][] jobs) {
//1. 대기 큐를 우선순위 큐로 생성
PriorityQueue<Job> pq = new PriorityQueue<>();
//2. 작업을 요청 시간 순으로 정렬
List<Job> list = new ArrayList<>();
for(int i = 0; i < jobs.length; i++){
list.add(new Job(i, jobs[i][0], jobs[i][1]));
}
Collections.sort(list, new JobStartTimeComparator());
//3. 요청 시간이 같은 작업들을 while문으로 돌려서 대기 큐에 넣기.
int curTime = list.get(0).getStartTime();
while(!list.isEmpty() && curTime == list.get(0).getStartTime()){
pq.add(list.remove(0));
}
List<Integer> returnTime = new ArrayList<>();
//4. while문 반복
while(true){
//5. 대기 큐에서 작업 꺼낸 후 반환 시간 계산 해 넣기
Job job = pq.poll();
int startTime = job.getStartTime();
int endTime = curTime + job.getCost();
returnTime.add(endTime - startTime);
//6. 작업 종료 시간까지의 작업들을 while문 돌려서 대기 큐에 넣기.
while(!list.isEmpty() && list.get(0).getStartTime() <= job.getCost() + curTime){
pq.add(list.remove(0));
}
//7. 작업 종료에 따른 시간 갱신
curTime += job.getCost();
//8. 만약 큐가 비어있는데, 남은 작업이 있을경우
if(pq.size() == 0 && !list.isEmpty()){
pq.add(list.remove(0));
curTime = pq.peek().getStartTime();
}
//9. 대기 큐도 비어있고, 남은 작업도 없을 때
if(pq.size() == 0) break;
}
//10. 반환 시간 List로 답 계산
int sum = 0;
for(int i = 0; i < returnTime.size(); i++){
sum += returnTime.get(i);
}
return sum / returnTime.size();
}
class JobStartTimeComparator implements Comparator<Job>{
@Override
public int compare(Job j1, Job j2){
if(j1.startTime > j2.startTime) return 1;
else if(j1.startTime < j2.startTime) return -1;
else return 0;
}
}
class Job implements Comparable<Job>{
private int num;
private int startTime;
private int cost;
public Job(int num, int startTime, int cost){
this.num = num;
this.startTime = startTime;
this.cost = cost;
}
public int getNum(){
return this.num;
}
public int getStartTime(){
return this.startTime;
}
public int getCost(){
return this.cost;
}
@Override
public int compareTo(Job job){
if(this.cost > job.getCost()) return 1;
else if(this.cost < job.getCost()) return -1;
else{
if(this.startTime > job.getStartTime()) return 1;
else if(this.startTime < job.getStartTime()) return -1;
else{
if(this.num > job.getNum()) return 1;
else return -1;
}
}
}
}
}
배운 점
우선순위 큐를 커스텀 정렬하고 싶을 때
class를 하나 생성하여 Comparable 인터페이스를 implements 하는 방법에 대해 배울 수 있었다.
'Problem Solving > [Java] Programmers' 카테고리의 다른 글
| [Java] 프로그래머스: 베스트앨범 (1) | 2025.01.18 |
|---|---|
| [Java] 프로그래머스: 디스크 컨트롤러 - 람다식 활용 (0) | 2025.01.18 |
| [Java] 프로그래머스: 가장 큰 수 (0) | 2025.01.18 |
| [Java] 프로그래머스: K번째수 (0) | 2025.01.18 |
| [Java] 프로그래머스: 전화번호 목록 (0) | 2025.01.12 |
