.programmers(디스크 컨트롤러)

https://programmers.co.kr/learn/courses/30/lessons/42627

 

1. 2022.04.08 시도

소요시간: 74분

//9:31 ~ 
import java.util.*;


class Job {
    public int start;
    public int duration;
    public int diff=0;

    Job(int start, int duration) {
        this.start = start;
        this.duration = duration;
    }
    
    public String toString() {
        return start + ":" + duration + "("+diff+")";
    }
}

class Solution {
    public int solution(int[][] jobs) {
        PriorityQueue<Job> pq = new PriorityQueue<>((o1, o2) -> {
            if (o1.start > o2.start) {
                return 1;
            } else if (o1.start < o2.start) {
                return -1;
            } else {
                if (o1.duration > o2.duration) {
                    return 1;
                } else if (o1.duration < o2.duration) {
                    return -1;
                } else {
                    return 0;
                }
            }
        });
        
        for (int i=0; i<jobs.length; i++) {
            pq.offer(new Job(jobs[i][0], jobs[i][1]));
        }
        
        int sum = 0;
        int timer = 0;
        while (!pq.isEmpty()) {
        	Job job = pq.poll();
            if (timer < job.start) {
            	timer = job.start + job.duration;
            } else {
            	timer += job.duration;
            }

            while(pq.size() > 0 && timer > pq.peek().start) {
                Job each = pq.poll();
                each.diff += timer - each.start;
                each.start = timer;
                pq.offer(each);
            }

            sum += job.duration + job.diff;
        }

        return sum/jobs.length;
    }
}

풀이 접근 과정

PriorityQueue를 중심으로 문제를 풀어본다.

시작 시점과 작업시간을 저장한 Job이라는 클래스를 선언하여 큐에 넣는다.
start는 시작시점, duration은 작업 시간, diff는 시작 시점과의 차이를 맞춰주는 필드다.

경과된 시간안에 시작된 작업이 있다면 큐에 다시 넣어준다. 시작시간은 현재 시점으로 리셋해주고 다만 나중에 평균 작업시간 계산을 위해 diff에 저장해둔다.

 

느낀점

• 솔직히 해맸다. 어떻게 비교할지에 대해 나중에 깨달았다. pq에서 pop후에 while문으로 다시 세팅해주는 로직이 생긴 이후로는 크게 어렵지 않았다.
• 그런데 sum/3으로 하드코딩해두어서 그거 찾는데 시간이 오래걸렸다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형

​