[프로그래머스/Lv. 3] 디스크 컨트롤러 (JAVA)

🔺 문제

프로그래머스

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
class Solution {
    public int solution(int[][] jobs) {
        int total = 0;
        int end = 0;    // 수행되고 난 직후 시간
        int idx = 0;    // jobs 배열의 인덱스
        int cnt = 0;    // 수행된 요청 갯수
 
        // 🔔 1. 작업 끝나는 시점이 들어온 요청에 대해 가장 짧은 수행시간 가진 작업 선택
        Arrays.sort(jobs, (o1,o2) -> o1[0] - o2[0]);
        
        // 🔔 2. 수행시간이 짧은 작업부터 처리 (우선순위 큐ㅡ Heap)
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        
        // 요청이 모두 수행될 때까지 반복
        while(cnt < jobs.length) {
            
            // 한 작업이 완료되는 시점(end)까지 들어온 모든 요청을 큐에 넣음
            while(idx < jobs.length && jobs[idx][0] <= end) {
                pq.add(jobs[idx++]);
            }
            
            // 큐가 비어있다면, 작업 완료(end) 이후 다시 요청이 들어옴
            if(pq.isEmpty()) {
                end = jobs[idx][0];
            }
            // 작업이 끝나기 전, 들어온 요청 중 가장 수행시간이 짧은 요청부터 수행
            else {
                int[] tmp = pq.poll();
                
               total += tmp[1] + end - tmp[0];
                end += tmp[1];
                cnt++;
            }
        }
        
        return total / jobs.length;
    }
}

✅ 해결 아이디어
✔ 힙 (Heap)
- 대기 시간을 최소로 줄여 요청되는 작업 수행하면 됨.
1) '작업 요청 시점'  짧은 순으로  오름차순 정렬
2)  '작업 소요 시간' 짧은 순으로 오름차순 정렬 (⭐ 우선순위 큐, Heap ⭐)

 

💥 유의사항

• 18번째 줄 | while(jobs.length --> 0) 했다가 런타임 에러 뜸..

 

 

---

🔺 다른 풀이들

- 새로 class 생성해서 정렬하셨다.

[프로그래머스] 디스크 컨트롤러 - Java

[프로그래머스] 디스크 컨트롤러 Java 풀이

 

 

- 로직은 같은데 주석이랑 이런 게 다 깔꼼해서 줍줍...

프로그래머스

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;

        // 작업이 요청되는 시점 기준으로 오름차순 정렬
        Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]);

        // 작업의 소요시간 기준으로 오름차순 정렬
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);

        int jobs_index = 0; // 작업 배열 인덱스
        int finish_job = 0; // 처리 완료된 작업 개수
        int end_time = 0; // 작업 처리 완료 시간

        while(true) {
            if(finish_job == jobs.length) break; // 모든 작업을 처리했다면 종료

            // 이전 작업 처리 중 요청된 작업 add
            while(jobs_index < jobs.length && jobs[jobs_index][0] <= end_time) {
                pq.add(jobs[jobs_index++]);
            }

            if(!pq.isEmpty()) { // 이전 작업 처리 중 요청된 작업이 있는 경우
                int[] job = pq.poll();
                answer += end_time - job[0] + job[1]; // 작업 요청부터 종료까지 걸린 시간 추가
                end_time += job[1]; // 작업 처리 완료 시간 갱신
                finish_job++; // 처리 완료된 작업 개수 1 증가
            } else { // 이전 작업 처리 중 요청된 작업이 없는 경우
                end_time = jobs[jobs_index][0]; // 다음 작업 요청 시점으로 갱신
            }
        }

        return answer / jobs.length;
    }
}

---

💬 느낀 점

 작업 수행 시간( 2차원 배열의 2번쨰 값)이 짧은 순으로 정렬하고

누적합 사용해서 푸면 되는 거 아닌가 했는데 틀렸었다..ㅠ

 

풀고 나니 어려운 문제가 아닌데 참....ㅠ

복습을 허자!!!

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

- 풀이

프로그래머스_힙(Heap)_디스크 컨트롤러 (JAVA)

 

 

- 2차원 배열 정렬 (둘째 값 기준 정렬)

[Java] 2차원 배열 정렬 (오름차순, 내림차순, 다중 조건)