PCCP 모의고사 1회 - 운영체제

1. 문제 정의

2. 문제 접근

PriorityQueue를 써서 대기열에 넣었다가, 하나씩 꺼내서 실행시키면서 각 점수마다 대기시간을 갱신시켜 주면 된다.

3. 문제 풀이

1. Program Class 를 정의한다.
  1.1 Comparable 인터페이스를 구현해 정렬 기준을 준다. 
    1.1.1. 점수가 같다면 호출 순서가 작은 것부터(오름차순)
    1.1.2. 만약 점수가 다르다면 점수가 더 낮은 것 부터(오름차순)

2. 본 로직 실행 전에 program 입력 값을 정렬해 준다.
  2.1 점수가 더 낮은 순서대로(오름차순)

3. 실행 순서대로 queue에 담고, 하나씩 실행시킨다.

4. 정답을 return 한다.

4. 코드

import java.util.*;

class Solution {

    // score: 점수, call 호출 시각, run : 실행 시간
    class Program implements Comparable<Program> {
        int score;
        int call;
        int run;

        Program(int p, int c, int r) {
            this.score = p;
            this.call = c;
            this.run = r;
        }

        @Override
        public int compareTo(Program p) {
            //  우선순위가 같다면 call이 오름차순으로 정렬
            if (this.score == p.score) return Integer.compare(this.call, p.call);
            //  만약 우선순위가 다르다면 score가 오름차순으로 정렬
            return Integer.compare(this.score, p.score);
        }
    }

    //{a,b,c}: a: 점수, b : 호출 시각, c:실행 시간
    public long[] solution(int[][] program) {
        long[] answer = new long[11];

        // 먼저 호출 순서대로 program 배열 정렬하기
        Arrays.sort(program, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[1], o2[1]);
            }
        });
        // 실행 순서가 되면 queue에 넣는다.
        PriorityQueue<Program> queue = new PriorityQueue<>();
        // <우선순위, 대기시간>
        Map<Integer, Long> wait_time = new HashMap<>();
        // 실행되기 위해 queue 에 들어가는 program
        int in = 0;
        // 실행 시간
        int time = 0;
        Program curr_program = null;
        // program : 0 - 점수 / 1 - 호출 시각 / 2 - 실행 시간
        while (true) {
            // 대기열 등록 가능한 프로그램 모두 등록하기
            while (in < program.length && program[in][1] == time) {
                queue.add(new Program(program[in][0], program[in][1], program[in][2]));
                in++;
            }

            // 실행중인 프로그램 시간 늘리기(실행시키기)
            if (curr_program != null) {
                curr_program.run--;
                if (curr_program.run == 0) curr_program = null;
            }

            // 프로그램 실행 끝났으면
            if (curr_program == null) {
                // 대기중인거 있으면 실행 시작
                if (!queue.isEmpty()) {
                    curr_program = queue.remove();
                    wait_time.put(curr_program.score, wait_time.getOrDefault(curr_program.score, 0L) + (time - curr_program.call));
                }
                // 없으면 최종 종료시간 계산 후 종료
                else if (in >= program.length) break;
            }
            time++;
        }

        answer[0] = time;
        for (int key : wait_time.keySet()) {
            answer[key] = wait_time.get(key);
        }

        return answer;

    }
}

5. 회고

Queue를 활용한 문제들이 많이 출제되는 것 같다. 실행 우선 순위가 있고, Comparable 이나 Comparator 같은 인터페이스를 상속 받아 구현하는 부분까지 고려해야 하기 때문에 상당히 어렵게 느껴졌다. 많이 연습해야 할듯!