[JAVA] Programmers <Heap LV3> 디스크 컨트롤러

또, 예시가 1개뿐인 문제를 만났다. 상당히 복잡해 보이는 문제지만, 대기 시간이 0인 작업을 먼저 처리해주고 그다음에 작업 시간이 짧은 작업 순으로 처리하여 평균 시간을 구하면 풀릴 줄 알았다...

---

package com.choonham;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public int solution(int[][] jobs) {
    	
    	int disk = 0;
    	int sum = 0;
        int answer = 0;
        List<int[]> tempArray = new ArrayList<>();
        PriorityQueue<int []> pq = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return (o1[1] < o2[1] ? -1 : ((o1[1] == o2[1]) ? 0 : 1));
			}
        });
        
        for(int i = 0; i <  jobs.length; i++) {
        	pq.add(jobs[i]);
        }
        
        while(true) {
        	
        	int[] curPro = pq.poll();
        	if(curPro[0]==0) {
        		sum += curPro[1];
        		disk += curPro[1];
        		break;
        	}
        	else {
        		tempArray.add(curPro);
        	}
        }
        for(int i = 0; i < tempArray.size(); i++) {
        	pq.add(tempArray.get(i));
        }
       
        
       while(true) {
    	   if(pq.isEmpty()) break;
    	   int[] curPro = pq.poll();
    	   System.out.println(curPro[1]);
    	   disk += curPro[1];
    	   sum += (disk - curPro[0]);
       }
       
       
       answer = sum / jobs.length;
       
        
        return answer;
    }
}

이렇게 구성하여 예시 코드를 돌려보면,

통과는...한다. 그러나 감출 수 없는 불안감..

그냥 실패도 아니고 무려 런타임 에러로 결과가 도배가 된다. ㅠㅅㅠ(와중에 20번은 왜 맞는지도 모르겠다.)

항상 생각하는건데, 프로그래머스의 연습문제들은 테스트 케이스나 부가 설명이 너무 불친절하다.

 

---

아마 대기 시간이 0인 작업이 중복으로 들어오는 경우를 처리 못해서 저렇게 많은 런타임 에러가 나오는 것 같아, 그 분을 수정하고 다시 돌려봤다.

---

package com.choonham;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public int solution(int[][] jobs) {
    	
    	int disk = 0;
    	int sum = 0;
        int answer = 0;
        boolean toggle = true;
        List<int[]> tempArray = new ArrayList<>();
        PriorityQueue<int []> pq = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return (o1[1] < o2[1] ? -1 : ((o1[1] == o2[1]) ? 0 : 1));
			}
        });
        
        for(int i = 0; i < jobs.length; i++) {
        	tempArray.add(jobs[i]);
        }
        
        for(int i = 0; i < tempArray.size(); i++) {
        	if(tempArray.get(i)[0] == 0 && toggle){
        		disk += tempArray.get(i)[1];
        		sum += tempArray.get(i)[1];
        		toggle = false;
        	} else {
        		pq.add(tempArray.get(i));
        	}
        }
        
        while(true) {
     	   if(pq.isEmpty()) break;
     	   int[] curPro = pq.poll();
     	   disk += curPro[1];
     	   sum += (disk - curPro[0]);
        }
        
        
        answer = sum / jobs.length;

        /*
        Iterator itr = pq.iterator();
        while(itr.hasNext()) {
        	int[] temp = (int[])itr.next();
        	System.out.println(temp[1]);
        }
        */

        
        return answer;
    }
}

뭐...결론적으로 런타임 에러는 지우긴 지웠는데... 좀 더 생각해볼 필요가 있을 거 같다...ㅠ

---

이쯤 되니 대기 시간이 0인걸 무작정 찾는 건 별 도움이 안되는 것 같다... 

질문 게시판에 올라와 있는 여러 반례 중 좀 괜찮아 보이는 테스트케이스를 하나 더 가져와 천천히 디버깅해보며 문제를 다시 이해해봤다.

 

가져온 테스트 케이스: {{0,20},{3,4},{3,5},{17,2}}

또한, 현재 디스크가 읽고 있는 위치를 고려하지 않고 무조건 작업을 순서대로 빼내려고 했던 것도 틀린 부분 중 하나라고 생각이 들어 코드를 전부 지우고 다시 풀었다. (하하...)

그러다가 발견한 문구 하나...!

"먼저 요청이 들어온 작업"

즉,

1. 배열의 순서를 그대로 따르는 것이 아니라, 들어온 jobs 배열 또한 요청 시간 순서로 정렬해주는 작업을 먼저 해야한다는 것!!!!

2. disk의 위치보다 요청 시간이 짧은 작업들만 pq에 추가하고, 우선 실행시켜줘야 한다. 

 

위에 있는 두 코드는 이 두가지 작업이 모두 빠져 있어서 테스트 케이스에서 주는 작업이 조금만 많아지면 바로 순서가 꼬이게 되니 실패했던 것이었다.... 

 

애초에 처음에 제시해주는 테스트 케이스가 워낙 작업이 적기도 했고, 내가 문제 이해를 잘못한 것도 있어서...꽤나 오랜 시간 고민했다. 

뭐 어쨋든 위 두가지를 명심하고 다시 구현해보면,

---

package com.choonham;


import java.util.Arrays;
import java.util.Comparator;

import java.util.PriorityQueue;

class Solution {
    public int solution(int[][] jobs) {
    	
    	int disk = 0;
    	
    	int sum = 0;
    	
        int answer = 0;
        
        int len = jobs.length;
        
        int idx = 0;
      
        PriorityQueue<int []> pq = new PriorityQueue<>(new Comparator<int[]>() {   // 요청 시간에 맞는 순서대로 작업을 처리할 우선 순위 큐
			@Override
			public int compare(int[] o1, int[] o2) {
				return (o1[1] < o2[1] ? -1 : ((o1[1] == o2[1]) ? 0 : 1));
			}
        });
        
        Arrays.sort(jobs, new Comparator<int[]>() {   //Jobs를 요청 시간이 짧은 순서로 정렬
			@Override
			public int compare(int[] o1, int[] o2) {
				return (o1[0] < o2[0] ? -1 : ((o1[0] == o2[0]) ? 0 : 1));
			}
        });
        
       while(idx < len || !pq.isEmpty()) {      // 현재 가리키는 인덱스가 jobs 배열 안쪽이거나 pq가 1개 이상 들어있다면 루프
    	   while(idx < len && jobs[idx][0] <= disk) {  //현재 가리키는 인덱스가 jobs 배열 안쪽이거나,
    		   pq.add(jobs[idx]);                                                   // 선택한 작업의 요청 시간이 현재 disk와 같거나 작다면
    		   idx++;                                                                              // pq에 해당 작업을 추가하고, 다음 인덱스로 간다.
    	   }
    	   if(pq.isEmpty()) {                                     //현재 pq가 비어있나? ->  현재 진행 중인 작업이 있는가?
    		   disk = jobs[idx][0];                            // yes -> disk의 위치는 현재 인덱스의 요청 시간
    	   } else {
    		   int temp[] = pq.poll();                       //no -> pq에 들어간 작업을 수행
    		   sum  += disk - temp[0] + temp[1];   // 작업 당 요청부터 완료까지 걸리는 시간 누적
    		   disk += temp[1];                                  // disk의 위치를 해당 작업이 완료된 순간으로 이동
    	   }
       }
        
        
        answer = sum / jobs.length;   


        
        return answer;
    }
}

질문 게시판에 있는 반례들의 결과가 모두 맞는 걸 보면 정답이지싶다.

LV3인 만큼 꽤나 삽질을 한 뒤에 정답을 맞췄지만, 솔직히 5개 이상의 작업을 가지고 있는 테스트 케이스 2개 정도만 예시로 더 줬더라면 문제 이해가 조금이라도 더 쉬웠을 것 같다.