프로그래머스 Lv.3) 디스크 컨트롤러 (HEAP)

프로그래머스 고득점 Kit - HEAP

디스크 컨트롤러

코딩테스트 연습 - 디스크 컨트롤러

풀이

 

저번에 풀었을 때보다 더 빨리 풀기는 했지만, 이놈의 고질병인 문제를 대충 읽는다는게 발목을 계속 잡는다.

정말 중요한 부분인데, 사소한거 하나에 꼬이게 되면 정말 골치가 아프다...

문제 제발 꼼꼼하게 읽자...

 

문제에서 막혔던 부분을 떠올려보자면,

대기시간을 구하는 방법, 작업 간 공백이 있을 때 시간을 구하는 방법 정도가 되겠다.

대기시간은 몇 번 삽질끝에 쉽게 구했는데, 공백기도 대기시간으로 포함해서 풀면서 시간을 많이 잡았다.

공백기는 대기시간이 아니기 때문에, 시간을 잡아줄 필요가 없었다.

대신 일을 진행하고있는 시간에 대해서는 공백기를 뛰어넘어야 풀 수 있는 문제였다.

 

첫번째로 짰던 코드는 두개의 우선순위큐를 이용해서 풀었고, 이번에 풀때는 우선순위 큐와 ArrayList 각각 하나씩 이용해서 풀었다.

효율은 오늘 풀었던 것이 더 좋다고 생각한다. ArrayList 정렬에 쓰이는 Comparator를 다뤄보고자 써봤는데, 더 좋은 방법이 있을거라고는 생각한다.

 

로직

 

1. 작업 배열을 ArrayList에 담아 시작 시간이 빠른 순서대로, 시간이 같다면 작업시간이 제일 짧은 순서대로 정렬한다.

2. 첫번째로 해야하는 작업을 우선순위 큐에 담아 반복문을 진행한다.

3. 답이 들어갈 시간과, 일이 진행되고 있는 시간을 따로 설정해서 각각 움직인다.

4. 공백기가 있으면, 일이 진행되는 시간을 공백기 이후 시작하는 작업 시간에 맞춰 주어야 한다는 점과 대기 시간이 있다면 대기시간을 더해줘야한다는 점을 유의한다.

 

코드 1

 

import java.util.PriorityQueue;

class Solution {
    public int solution(int[][] jobs) {
        int answer =0;
        int jobCnt = jobs.length;

        PriorityQueue<WaitJob> waitQueue = new PriorityQueue<>();
        PriorityQueue<Job> jobQueue = new PriorityQueue<>();

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

        WaitJob startJob = waitQueue.poll();    // 기준
        jobQueue.offer(new Job(startJob));
        while(!waitQueue.isEmpty()) {
            WaitJob wait = waitQueue.poll();
            if(startJob.st == wait.st) {
                jobQueue.offer(new Job(wait));
            } else {
                waitQueue.offer(wait);
                break;
            }
        }

        int time = 1000;  // 최대 1000초 까지 작업이 들어올 수 있음
        int prevEnd = 0;

        for(int i=0; i<=time; i++) {

            while(!waitQueue.isEmpty()) {
                WaitJob wait = waitQueue.poll();
                if(wait.st <= i) {
                    jobQueue.offer(new Job(wait));
                } else {
                    waitQueue.offer(wait);
                    break;
                }
            }

            while(!jobQueue.isEmpty()) {
                Job job = jobQueue.poll();

                if(prevEnd <= i) {
                    // 중간에 작업이 뜨는 기간이 아닐때는 대기시간 구해주고, 아닐 때는 대시기간 0으로 초기화
                    int watingTime = (prevEnd == i && job.startTime < i) ? prevEnd - job.startTime : 0;

                    time += job.workTime;
                    answer += job.workTime + watingTime; // 진행 시간에 대기시간 더해주기
                   prevEnd =prevEnd < job.startTime ? job.startTime + job.workTime : i+job.workTime; // 진행시작한 작업이 끝나는 시점 저장

                    // prevEnd = i+job.workTime;
                } else {
                    jobQueue.offer(job);
                    break;
                }
            }
        }

        return answer/jobCnt;
    }
}

class WaitJob implements Comparable<WaitJob> {
    int st;
    int wt;

    public WaitJob(int st, int wt) {
        this.st = st;
        this.wt = wt;
    }

    @Override
    public int compareTo(WaitJob job) {
        return this.st >= job.st ? 1 : -1;
    }
}

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

    public Job (WaitJob job) {
        this.startTime = job.st;
        this.workTime = job.wt;
    }

    @Override
    public int compareTo(Job job) {
        return this.workTime >= job.workTime ? 1 : -1;
    }
}

 

코드 2

 

import java.util.PriorityQueue;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Collections;

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        
        ArrayList<int[]> waitList = new ArrayList<>();
        PriorityQueue<Task> taskQ = new PriorityQueue<>();
        
        for(int[] job : jobs) {
            waitList.add(job);
        }
        
        Collections.sort(waitList, new Comparator<int[]>() {
            @Override
            public int compare(int[] v1, int[] v2) {
                if(v1[0] > v2[0]) {
                    return 1;
                } else if(v1[0] == v2[0]) {
                    return v1[1] >= v2[1] ? 1: -1;
                } 
                return -1;
            }
        });
        int[] start = waitList.get(0);
        answer = 0;  
        taskQ.offer(new Task(start[0],start[1]));
        waitList.remove(0);
        int nowTime = start[0]; // 일을 진행할 시간
        
        while(!taskQ.isEmpty()) {
            Task task = taskQ.poll();
            answer += Math.abs(nowTime-task.start) + task.time;
            nowTime +=  task.time;
            
            int min=1001;
            int idx=0;
            for(int i=0; i<waitList.size(); i++) {
                int[] target = waitList.get(i);
                if(target[0] <= nowTime) { // 시작 시점이 현재 시간보다 빠른 경우
                    if(min > target[1]) {
                        min = target[1];
                        idx = i;
                    }
                }
            }
            if(waitList.size() !=0) {
                int[] tmp = waitList.get(idx);
                if(min == 1001) {
                    nowTime = tmp[0];
                }
                taskQ.offer(new Task(tmp[0],tmp[1]));
                waitList.remove(idx);
            }
        }
        return answer/jobs.length;
    }
}

class Task implements Comparable<Task>{
    int start;
    int time;
    
    public Task(int start, int time) {
        this.start = start;
        this.time = time;
    }
    
    @Override
    public int compareTo(Task t) {
        return this.time >= t.time ? 1 : -1;
    }
}