[Programmers] 힙.디스크 컨트롤러 / Heap

@Heap / 30m

정렬 조건을 어떻게 줘야 하는지 난해해서 고민을 좀 했다.

 

문제 링크

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

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

 

 

문제 유형

맨날 풀던 유형들과는 조금 결이 다른 문제여서 살짝 당황했었다.

 

풀고 나서 구글링을 해봤더니 OS에 이 개념과 관련된 알고리즘이 있었다.

와우.. 잘 알려진 알고리즘인데 그게 이거일 줄이야..

     > SPN(Shortest Process Next) / SJF(Shortest Job First)

 

     + 정확한 개념을 알고 싶으신 분은 여기에 굉장히 설명이 잘 되어 있으므로 참고하시면 좋을 것 같다.

 

이 글과 내 코드는 구현 방식은 같으나 (대기큐와 작업큐를 이용해서 구현함)

정확하게 알고 구현하는 것과 잘 모르고 구현하는 것은 다르니까 공부해야겠다고 생각했다.

(개념을 잘 모르는 상태에서도 구현해서 맞춘 건 뿌듯 + 개념을 몰랐던건 아쉽)

 

안그래도 요새 OS 공부를 해야겠다 생각하던 차에, 좋은 계기가 되었다.

지금 강의 3강인데 강의 중반쯤에 해당 내용이 있어서 얼른 들어서 공부하고 싶다는 생각이 들었다.

공부를 다 하고 나중에 포스팅을 할까 하다가,

그래도 OS 공부의 중요성을 다시 한번 깨닫게 된 계기라서, 일단 써두기로 했다.

OS 개념을 공부하고 나서 다시 풀어봐야겠다.

     + OS 공부를 시작했다!

 

 

코드

굉장히.. 지저분하다 얼른 고치고 싶음 ㅜㅜ

 

import java.util.*;

class Solution {
    //waitingPQ에 넣을 애들은 시작시간이 빠른 순으로, 그리고 시작시간이 같다면 짧은 순으로
    class Node implements Comparable<Node>{
        int start, time;
        Node (int start, int time) {
            this.start = start;
            this.time = time;
        }
        @Override
        public int compareTo (Node o) {
            if (this.start != o.start) {
                return this.start - o.start;
            }
            return this.time - o.time;
        }
    }
    
    //workingPQ에 넣을 애들은 작업 시간이 짧은 순으로
    class Node2 implements Comparable<Node2>{
        int start, time;
        Node2 (int start, int time) {
            this.start = start;
            this.time = time;
        }
        @Override
        public int compareTo (Node2 o) {
            if (this.time != o.time) {
                return this.time - o.time;
            }
            return this.start - o.start;
        }
    }
    
    public int solution(int[][] jobs) {
        PriorityQueue<Node> waitingPQ = new PriorityQueue<Node>();
        PriorityQueue<Node2> workingPQ = new PriorityQueue<Node2>();
        
        for (int i = 0; i < jobs.length; i++) {
            waitingPQ.add(new Node(jobs[i][0], jobs[i][1]));
        }
        
        int answer = waitingPQ.peek().time;                                     
        int now = waitingPQ.peek().start + waitingPQ.peek().time;
        waitingPQ.poll();
        
        while (!waitingPQ.isEmpty() || !workingPQ.isEmpty()) {
            //now보다 시작시간이 더 이전에 있는 애들을 다 workingPQ에 담는다
            while (!waitingPQ.isEmpty() && waitingPQ.peek().start < now) {
                workingPQ.add(new Node2(waitingPQ.peek().start, waitingPQ.peek().time));
                waitingPQ.poll();
            }
            
            //만약 workingPQ가 비어있다면 (== now보다 시작시간이 빠른 애가 없다면)
            if (workingPQ.isEmpty()) {
                //waitingPQ에서 가장 앞에 있는 애(시작시간이 가장 빠른 애)를 하나 빼서 workingPQ에 담는다
                now = waitingPQ.peek().start;
                workingPQ.add(new Node2(waitingPQ.peek().start, waitingPQ.peek().time));
                waitingPQ.poll();
            }
            
            //now 이전에 시작했다면 대기시간을 포함해서 더해주고
            if (workingPQ.peek().start <= now) {
                answer += (now - workingPQ.peek().start) + workingPQ.peek().time;
                now += workingPQ.peek().time;
            
            //now 이후에 시작했다면 대기시간은 포함하지 않는다
            } else {
                answer += workingPQ.poll().time;
                now = workingPQ.peek().start + workingPQ.peek().time;
            }
            workingPQ.poll();
        }
        return answer / jobs.length;
    }
}

그래도 재미있는 문제였다.

끝!