웹에 올린 결과는 틀림. 그러나 내가 맞다 생각한다.
문제는 아래와 같다.
- 작업이 [시작 시각, 작업 길이] 2차원 배열로 들어온다.
- 작업이 연속될 경우, 이 안에서 작업 길이를 짧은 순으로 정렬하여 실행한다.
- 각 작업에 대한 기다린 시간 + 작업 시간을 계산한다.
- 작업 개수를 총 시간으로 나눠준다.
여기에서 배열을 한번에 읽는다. 첫번째 작업 순서를 읽을 때, 모든 작업 순서를 결정할 수 있다. 예제 [[0, 3], [1, 9], [2, 6]] 순서에 마지막 2개를 더 들어온다고 하자. [[0, 3], [1, 9], [2, 6], [24,4], [20,7]].
엑셀 Calc로 그림을 그리면 아래와 같다.
작업A부터 작업E까지 읽을 때, 필요한 작업 시간(checkBar)을 정해야 한다. 이 작업 시간안에 들어오면 작업 시간을 적은 순서대로 정렬한다. 작업 시간을 넘어가면 다음 턴에 정렬해야 한다.
입력을 읽을 때, 24초에 들어온 작업과 20초에 들어온 작업을 결정할 수 있다. 다음과 같이 조정할 수 있다. 24초에 들어온 작업을 20초에 먼저 실행하면 작업D, 작업E를 하는데 총 11초 걸린다.
만약 들어온 순서대로 하면 작업D, 작업E를 14초에 한다. jobs을 읽을 때 뒤쪽 배열에 시간이 빠른 작업을 어떻게 처리할까? 이런 경우를 보면 jobs을 순서대로 읽으면 안된다. 모두 읽어서 빠른 순서대로 정리해야 한다.
하드 디스크가 놀고 있을 때 먼저 들어온 순서대로 한다는 제한이 있다. jobs[][]이 대기열이다. 현재 시각이 0초이고, jobs[0] = [1,2], jobs[1] = [2,5], jobs[2] = [0,4]이라 하자. 위 제한에 따르면 jobs[2]는 조정할 수 없어 실핼할 수 없다. 문제 조건에 jobs[i]는 항상 시작 시각이 늘어난다는 조건을 추가해야 한다. 이 조건이 있었으면 내가 이런 개고생 안했을 수 있었다. 웹은 틀렸다지만 난 맞았다고 정당화시키고 끝낸다.
문제는 이 코드를 웹에 올리면 runtime error로 검증할 수 없다. 우선순위 큐 문제에 너무 많은 시간을 보냈다.
import java.util.Collections;
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
// PriorityQueue<Student> ptrTestQ = new PriorityQueue<>();
// while (!sol.getQ().isEmpty())
// System.out.println(ptrTestQ.remove());
// 시작..
int[][] jobs = new int[5][2];
jobs[0][0] = 0;
jobs[0][1] = 3;
jobs[1][0] = 1;
jobs[1][1] = 9;
jobs[2][0] = 2;
jobs[2][1] = 6;
jobs[3][0] = 24;
jobs[3][1] = 4;
jobs[4][0] = 20;
jobs[4][1] = 7;
/*
* System.out.println("Jobs type은"+jobs.getClass().getTypeName());
*
*
*/
Solution sol = new Solution();
int answer = sol.solution(jobs);
System.out.println("여기");
System.out.println("답은 " + answer);
/*
* while (!sol.getQue().isEmpty()) System.out.println("sol.getQue내용은 " +
* sol.getQue().poll()); while (!sol.getQueOffset().isEmpty())
* System.out.println("sol.getQueOffset내용은 " + sol.getQueOffset().poll());
*/
}// void main
} // Main
class Solution {
public int solution(int[][] jobs) {
// 요청 대기시간이 보정된 큐.
PriorityQueue<Job> priqueJobsReversed = new PriorityQueue<>();
PriorityQueue<Job> priqueCheckReversed = new PriorityQueue<>();
// jobs을 class로 입력
for (int i = 0; i < jobs.length; i++) {
Job tmpJob = new Job(jobs[i][0], jobs[i][1]);
// timeStamp 기준 정렬
// setFlag와 세트로 같이 움직여야 됨.
priqueJobsReversed.add(tmpJob);
}
/*
* while (!priqueJobsReversed.isEmpty()) { System.out.println("timeStamp:" +
* priqueJobsReversed.peek().timeStamp + ", Duration: " +
* priqueJobsReversed.peek().duration); priqueJobsReversed.poll(); }
*/
PriorityQueue<Job> priqueJobs = new PriorityQueue<>(priqueJobsReversed.size(), Collections.reverseOrder());
priqueJobs.addAll(priqueJobsReversed);
// 복사..
PriorityQueue<Job> priqueJobsTmp = new PriorityQueue<>(priqueJobs);
boolean overlapped = false;
int startTime = 0;
int endTime = 0;
int preDuration = 0;
int preTimeStamp = 0;
int PolledDuration = 0;
int PolledTimeStamp = 0;
while (!priqueJobsTmp.isEmpty()) {
if (!overlapped) {
startTime = priqueJobsTmp.peek().timeStamp;
endTime = startTime + priqueJobsTmp.peek().duration;
}
preDuration = priqueJobsTmp.peek().duration;
preTimeStamp = priqueJobsTmp.peek().timeStamp;
priqueJobsTmp.poll();
if (!priqueJobsTmp.isEmpty()) {
PolledDuration = priqueJobsTmp.peek().duration;
PolledTimeStamp = priqueJobsTmp.peek().timeStamp;
} //if
else {
PolledTimeStamp = 0;
Job checkBar = new Job(startTime, endTime);
// 시간순으로 정렬
priqueCheckReversed.add(checkBar);
}
if (startTime + preDuration >= PolledTimeStamp) {
// overlapped를 true로 바꾸고, endTime을 연장
overlapped = true;
endTime = endTime + PolledDuration;
} //if
else {
// endTime 연장하지 않음.
// overlapped flag를 다시 false로 변경.
overlapped = false;
// 여기에서 priorityQueue에 넣음.
Job checkBar = new Job(startTime, endTime-1);
// 시간순으로 정렬
priqueCheckReversed.add(checkBar);
} // else
// System.out.println("현재 startTime" + startTime);
// System.out.println("현재 endTime" + endTime);
// Object[] testArry = priqueCheckReversed.toArray();
} // while
/*
* System.out.println("*****여기 확인*******"); while (!priqueJobsTmp.isEmpty())
* System.out.println(priqueJobsTmp.poll());
*/
// 거꾸로 만든 큐 순서를 뒤집음.
PriorityQueue<Job> priqueCheck = new PriorityQueue<>(priqueCheckReversed.size(), Collections.reverseOrder());
priqueCheck.addAll(priqueCheckReversed);
// System.out.println("큐 크기" + priqueCheckReversed.size());
int answer = 0;
PriorityQueue<Job> priqueJobsOder = new PriorityQueue<Job>();
int i = 1;
while (!priqueCheck.isEmpty()) {
// 시작시각 확인.
int startTimeCheck = priqueCheck.peek().timeStamp;
int endTimeCheck = priqueCheck.peek().duration;
int presentTime = priqueCheck.peek().timeStamp;
//check구간의 Jobs을 꺼낸 후, 우선순위 변경하여 다시 넣어줌.
while (!priqueJobs.isEmpty()) {
int tmpTimeStamp = priqueJobs.peek().timeStamp;
int tmpDuration = priqueJobs.peek().duration;
if (startTimeCheck <= tmpTimeStamp && tmpTimeStamp <= endTimeCheck) {
Job orderJob = new Job(tmpTimeStamp, tmpDuration);
orderJob.setFlag(true);
priqueJobsOder.add(orderJob);
priqueJobs.poll();
} // if
else
break;
} //while priqueJobs
//한턴 끝난 후 reverse order로 변경.
PriorityQueue<Job> priqueJobsOderNext = new PriorityQueue<>(priqueJobsOder.size(),
Collections.reverseOrder());
priqueJobsOderNext.addAll(priqueJobsOder);
while (!priqueJobsOderNext.isEmpty()) {
int delay = presentTime - priqueJobsOderNext.peek().timeStamp;
int tmpAnswer = delay + priqueJobsOderNext.peek().duration;
answer = answer + tmpAnswer;
System.out.println("answer = " + answer);
System.out.println("현재시각 = " + presentTime);
System.out.println("duration = " + priqueJobsOderNext.peek().duration);
System.out.println("delay = " + delay);
i++;
presentTime = presentTime + priqueJobsOderNext.peek().duration;
priqueJobsOderNext.poll();
priqueJobsOder.poll();
} //while (priqueHobsOrderNext)
priqueCheck.poll();
} //while priqueCheck
answer = answer / (i - 1);
return answer;
}// int solutions(int[][] jobs)
}
class Job implements Comparable<Job> {
int duration;
int timeStamp;
boolean flag;
// 기본 생성자.
Job() {
this.duration = 0;
this.timeStamp = 0;
this.flag = false;
}
// 생성자 작성.
Job(int timeStamp, int duration) {
this.timeStamp = timeStamp;
this.duration = duration;
this.flag = false;
}
@Override
public int compareTo(Job arg0) {
// TODO Auto-generated method stub
if (!this.flag)
// TimeStamp가 큰 순서대로 poll;
return this.timeStamp < arg0.timeStamp ? 1 : -1;
else
// Duration이 큰 순서대로 poll
return this.duration < arg0.duration ? 1 : -1;
}
@Override
public String toString() { // TODO Auto-generated method stub
return "시각" + this.timeStamp + ", 기간" + this.duration;
}
public void setFlag(boolean flag) {
this.flag = flag;
}
} // Job