[PCCP 모의고사 #1] 4번 - 운영체제

https://school.programmers.co.kr/learn/courses/20847/lessons/255903

 

 

 

 

 

 

자료구조

우선순위 큐 두 개를 활용해야 합니다.

메모리에 올라가지 않은 프로그램을 위한 우선순위 큐, 메모리에 올라간 프로그램을 위한 우선순위 큐

우선순위를 결정하는 기준이 다르기 때문입니다.

- 메모리에 올라가지 않은 프로그램을 위한 우선순위 큐의 기준 : 프로그램 호출 시간

- 메모리에 올라간 프로그램을 위한 우선순위 큐의 기준 : 프로그램 우선순위 + 프로그램 호출시간

class Program{
    int score, callTime, runTime;
    
    public Program(int score,int callTime, int runTime){
        this.score = score;
        this.callTime = callTime;
        this.runTime = runTime;
    }
}

PriorityQueue<Program> left = new PriorityQueue<>((p1,p2)->(p1.callTime-p2.callTime));

PriorityQueue<Program> load = new PriorityQueue<>((p1,p2)->{
       if(p1.score==p2.score) return (p1.callTime-p2.callTime);
       return (p1.score-p2.score);
});

 

풀이과정

 

1. 현재시간(time)을 계속 증가시키면서 left 큐를 load큐로 다 옮겨주면서 현재시간(time)에 load큐에서 실행시킬 수 있는 프로그램 실행시키기

우선 현재 시간(time)을 기준으로 load 큐로 옮길 수 있는 프로그램들을 다 load큐로 옮겨줍니다.

 

그런 다음 현재 시간(time)에서 실행시킬 수 있는 프로그램을 실행시킵니다. 그리고 time 을 프로그램의 수행시간 만큼갱신합니다. 

 

만약 실행시킬 프로그램이 없다면 time을 1 증가 시킵니다.

// time을 계속 증가시키면서 left큐를 load 큐로 다 옮기는 작업
while(true){
            
      while(!left.isEmpty() && left.peek().callTime <= time){ // 현재 시간(time)을 기준으로 left 에서 load 큐로 옮기기
           load.offer(left.poll());
      }
            
      if(!load.isEmpty() && load.peek().callTime <= time){ // 현재 시간(time)에 실행할 작업이 있는 경우 (time을 runTime만큼 증가)
           Program cur = load.poll();
           answer[cur.score] += (time - cur.callTime);
           time += cur.runTime;
      }else{ // 현재 시간(time)에 실행할 작업이 없는 경우 (time을 1증가)
           time += 1;    
      }
            
      if(left.isEmpty()) break; // left 가 다 비워진 상태면 반복문 종료
}

 

2. load 큐에 남아있는 프로그램  수행

 // load 큐에 남아 있는 작업을 수행하는 코드
while(!load.isEmpty()){
      Program cur = load.poll();
            
      answer[cur.score] += (time - cur.callTime);
      time += cur.runTime;            
}

 

 

알게된 점

• 우선순위 큐 두 개를 두고, 두 큐 사이에 값을 전달하면서 문제를 해결할 수 있음을 알게되었습니다.
  • 두 큐를 다 비우는 시기가 다르므로, 한 큐가 다 비워진 다음 다른 큐를 비워주는 작업을 해줘야 함을 알게되었습니다.
• 간단해 보였는데 우선순위 큐를 두 개 활용한다는 점과, 두 우선순위큐가 비워지는 시기가 달라서 구현하기 까다로웠고, 결국 다른 사람의 코드를 참고해야 했습니다.

 

전체코드

import java.util.*;

class Program{
    int score, callTime, runTime;
    
    public Program(int score,int callTime, int runTime){
        this.score = score;
        this.callTime = callTime;
        this.runTime = runTime;
    }
}

class Solution {
    
    public long[] solution(int[][] program) {
        long[] answer = new long[11];
        long time = 0l;
        
        PriorityQueue<Program> left = new PriorityQueue<>((p1,p2)->(p1.callTime-p2.callTime));
        PriorityQueue<Program> load = new PriorityQueue<>((p1,p2)->{
            if(p1.score==p2.score) return (p1.callTime-p2.callTime);
            return (p1.score-p2.score);
        });
        
        for(int i=0;i<program.length;i++){
            left.offer(new Program(program[i][0],program[i][1],program[i][2]));
        }
        
        // time을 계속 증가시키면서 left큐를 load 큐로 다 옮기는 작업
        while(true){
            
            while(!left.isEmpty() && left.peek().callTime <= time){ // 현재 시간(time)을 기준으로 left 에서 load 큐로 옮기기
                load.offer(left.poll());
            }
            
            if(!load.isEmpty() && load.peek().callTime <= time){ // 현재 시간(time)에 실행할 작업이 있는 경우 (time을 runTime만큼 증가)
                Program cur = load.poll();
                answer[cur.score] += (time - cur.callTime);
                time += cur.runTime;
            }else{ // 현재 시간(time)에 실행할 작업이 없는 경우 (time을 1증가)
                time += 1;    
            }
            
            if(left.isEmpty()) break; // left 가 다 비워진 상태면 반복문 종료
        }
        
        // load 큐에 남아 있는 작업을 수행하는 코드
        while(!load.isEmpty()){
            Program cur = load.poll();
            
            answer[cur.score] += (time - cur.callTime);
            time += cur.runTime;            
        }
        
        answer[0] = time;
        
        return answer;
    }
}