프로그래머스 디스크컨트롤러

웹에 올린 결과는 틀림. 그러나 내가 맞다 생각한다.

문제는 아래와 같다.

1. 작업이 [시작 시각, 작업 길이] 2차원 배열로 들어온다.
2. 작업이 연속될 경우, 이 안에서 작업 길이를 짧은 순으로 정렬하여 실행한다.
3. 각 작업에 대한 기다린 시간 + 작업 시간을 계산한다.
4. 작업 개수를 총 시간으로 나눠준다.

여기에서 배열을 한번에 읽는다. 첫번째 작업 순서를 읽을 때, 모든 작업 순서를 결정할 수 있다. 예제 [[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