프로그래머스 PCCP모의고사#1 4번문제

💡 문제 요약

1. 호출된 프로그램 중 점수가 낮은 것부터 실행
2. 점수가 같다면 먼저 호출된 것부터 실행
3. 실행 가능한 프로그램이 없으면 가장 가까운 호출 시간으로 점프
4. 실행 도중에는 다른 프로그램이 와도 큐에 넣기만 하고 무시

• 각 점수별 대기 시간 누적합과 전체 실행 완료 시간을 반환

---

🧠 문제 배경

• OS 스케줄링, 이벤트 루프, 대기열 처리 등에서 사용되는 우선순위 기반 작업 실행 시뮬레이션
• 점수는 우선순위, 호출 시간은 정렬 기준, 실행 시간은 점유 시간으로 작용

---

🔍 알고리즘 설계

1️⃣ 입력 정렬

• 호출 시간을 기준으로 오름차순 정렬

2️⃣ 우선순위 큐 사용

• score 오름차순 → 호출 순 인덱스 오름차순으로 실행할 작업을 관리

3️⃣ 실행 흐름

• 현재 시간 기준으로 실행 가능한 작업을 큐에 추가
• 큐가 비어있으면 다음 호출 시간으로 점프
• 큐에서 가장 우선순위 높은 작업을 꺼내 실행
• 실행 시간만큼 현재 시간 증가 + 대기 시간 누적

---

💻 핵심 구현 코드

Arrays.sort(program, Comparator.comparingInt(p -> p[1]));

PriorityQueue<int[]> waitQ = new PriorityQueue<>(
    Comparator.comparingInt((int[] a) -> a[0])      // 점수
              .thenComparingInt(a -> a[3])          // 호출 순
);

int time = 0;
int idx = 0;

while (idx < program.length || !waitQ.isEmpty()) {
    while (idx < program.length && program[idx][1] <= time) {
        waitQ.offer(new int[]{program[idx][0], program[idx][1], program[idx][2], idx});
        idx++;
    }

    if (waitQ.isEmpty()) {
        time = program[idx][1];
        continue;
    }

    int[] cur = waitQ.poll();
    int score = cur[0];
    int calledTime = cur[1];
    int runTime = cur[2];

    answer[score] += time - calledTime;
    time += runTime;
}

---

✅ 시간 복잡도 분석

단계	복잡도
정렬	O(N log N)
큐 삽입/삭제	O(log N)
전체 루프	O(N log N)
총합	O(N log N)

---

📌 정리

• score → 호출 순 복합 우선순위는 PriorityQueue로 쉽게 구현 가능
• 시간 점프 처리를 통해 불필요한 시간 낭비 없이 시뮬레이션 구현
• 각 점수별 대기 시간을 따로 배열에 저장하여 결과 처리