디스크 컨트롤러(프로그래머스, Java)

문제링크: https://programmers.co.kr/learn/courses/30/lessons/42627

코딩테스트 연습 - 디스크 컨트롤러 | 프로그래머스

알고리즘 설명:

작업이 진행된 시간동안 들어온 다른 작업들 중 가장 작업시간이 적게 걸리는 작업을 다음 작업으로 선택하는 알고리즘

• 맨 처음 Job 클래스를 jobs 배열의 값들을 startTime과 workTime으로 나누어 넣을 수 있도록 만들었다.

• PriorityQueue를 사용하여 workTime이 짧은 순으로 오름차순 정렬을 하였다.
• 여기서 객체를 PriorityQueue에 넣으면 어떤 변수를 비교해야할지 알려주어야 하므로 Comparable<>을 상속받아 compareTo를 오버라이딩하여 오름차순인 return this - object를 해준다.(내림차순은 반대)
• 정렬된 값들을 하나씩 poll()하여 list에 넣어준다.
• 진행된 시간안에 있는 작업들을 계산하여 값을 구하고 만약 진행된 시간안에 작업이 하나도 없다면 time을 1씩 늘려주어 진행 시간을 높혀준다.

막혔던 지점:

list를 대신 Queue를 사용하여 진행시간을 고려하지 않고 차례대로 받아 값을 계산하였다. 멍청했지...

작업시간은 짧지만 나중에 들어올 작업일 수도 있다는 점을 생각하지 않고 풀었더니 계속해서 실패가 나왔다.

 

package test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class DiskController {

	public static int solution(int[][] jobs) {

		int answer = 0;
		int time = 0;

		Queue<Job> queue = new PriorityQueue<>();
		Queue<Job> calcqueue = new LinkedList<>();
		List<Job> list = new ArrayList<>();

		for (int[] job : jobs) {
			queue.offer(new Job(job[0], job[1]));
		}

		for (int[] job : jobs) {
			list.add(queue.poll());
		}

		while (list.size() > 0) {
			for (int i = 0; i < list.size(); i++) {
				if (time >= list.get(i).startTime) {
					time += list.get(i).workTime;
					answer += time - list.get(i).startTime;
					list.remove(i);
					System.out.println("time :" + time + " answer: " + answer);
					break;
				}
				if (i == list.size() - 1)
					time++;
				System.out.println("-----time :" + time);
			}
		}

		answer /= jobs.length;

		return answer;

	}

	public static class Job implements Comparable<Job> {
		int startTime;
		int workTime;

		public Job(int startTime, int workTime) {
			this.startTime = startTime;
			this.workTime = workTime;
		}

		@Override
		public int compareTo(Job job) {

			return this.workTime - job.workTime;
		}
	}

	public static void main(String[] args) {

		int jobs[][] = { { 24, 10 }, { 18, 39 }, { 34, 20 }, { 37, 5 }, { 47, 22 }, { 20, 47 }, { 15, 34 }, { 15, 2 },
				{ 35, 43 }, { 26, 1 } };

		// int jobs[][] = { { 0, 3 }, { 1, 9 }, { 2, 6 } };
		System.out.println(solution(jobs));
	}

}