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

문제

코드

import java.util.*;
class Solution {
    public long[] solution(int[][] program) {
        long[] answer = new long[11];
        Queue<int[]> wait=new PriorityQueue<>((a,b)->a[1]-b[1]);
        Queue<int[]> arrive=new PriorityQueue<>((a,b)->{
            if(a[0]==b[0]) return a[1]-b[1];
            else return a[0]-b[0];
        });
        long time=0;
        for(int[] p:program)
            wait.add(p);
        
        while(!wait.isEmpty()||!arrive.isEmpty()){
            if(!wait.isEmpty()&&time>=wait.peek()[1]){
                while(!wait.isEmpty()&&time>=wait.peek()[1]){
                    arrive.add(wait.poll());
                }
            }
            if(!arrive.isEmpty()){
                answer[arrive.peek()[0]]+=time-arrive.peek()[1];
                time+=arrive.poll()[2];    
            }
            else if(!wait.isEmpty()) time=wait.peek()[1];
        }
        
        answer[0]=time;
        return answer;
    }
}

풀이

(1) 우선순위 큐 두개를 만든다.

• wait큐는 아직 호출되지 않은 작업들이 들어간다.(호출 시간 순)
• arrive 큐는 호출 되었지만 아직 진행되지 않은 작업들이 들어간다.(우선 순위 순, 우선 순위가 같을 시 호출 시간순)

(2) wait 큐에 모든 작업들을 넣어주고, 반복문을 시작한다.

• while 문은 wait 큐와 arrive 큐가 모두 비어있을 때 종료된다.
• 현재 시각 기준으로 호출 된 작업들을 wait 큐에서 arrive 큐로 옮겨준다.
• arrive 큐에 다음 진행할 작업이 있으면 그 작업에 대해 answer에는 대기시간을 더해주고, 시간에는 이 작업의 진행 시간만큼 더해준다.
• arrive 큐에 다음 진행할 큐가 없고, 아직 호출되지 않은 큐가 있다면 가장 빠른 호출시간을 가진 작업을 진행할 수 있도록 시간을 바꿔준다.

(3) answer[0] 에는 전체 진행시간이 들어가므로 time을 넣어주고 answer을 반환한다.

결과

분명 어려운 문제라고 생각하진 않았는데, 계속 채점에서 실패했다.
도저히 뭐가 잘못된 건지 찾을수가 없어서 3~4시간 정도 걸렸다.
내가 처음에 했던 방식은
현재 시간 기준으로 호출된 모든 작업을 arrive에 넣어주는데,
만약 호출된 작업이 없다면, 다음 가장 빠른 작업의 호출시간으로 시간을 바꿔버리고 continue를 해버렸다.
이렇게 하면 arrive에 작업이 있는데, 시간을 바꿔버리기 때문에 문제가 발생한다.

요즘 너무 감이 떨어진 것 같다.
분명 간단하게 해결할 수 있는 문제였는데도 푸는데 어려움이 있었다.
정말 잘하고 싶은데, 알고리즘은 실력을 올리기가 너무 어려운 것 같다.

출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges