프로그래머스 알고리즘 (java)
디스크 컨트롤러
코드 리뷰
각 작업에 대해 [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열 jobs가 매개변수로 주어질 때, 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마가 되는지 return 하도록 solution 함수를 작성해주세요. (단, 소수점 이하의 수는 버립니다)
요청이 그림과 같이 들어온다면
두가지 경우의 수가 있습니다.
-
A → B → C
A → B → C이 때 각 작업의 요청부터 종료까지 걸린 시간의 평균은10ms(= (3 + 11 + 16) / 3)가 됩니다.
-
A → C → B
A → C → B의 순서로 처리하면 각 작업의 요청부터 종료까지 걸린 시간의 평균은9ms(= (3 + 7 + 17) / 3)가 됩니다.
따라서 A → C → B 로 처리한 평균 9ms 가 return 됩니다.
조건
- 현재 시간에 사용할 수 있는 요청이 처리된다.
- 처리된 후 처리될 수 있는 요청중 평균값이 작게 나오는 요청을 먼저 처리한다.
- 딜레이가 작은 값을 먼저 처리하는게 평균값이 낮게 나온다.
- 요청으로 부터 작업의 종료 시점은
현재시간 + delayTime - index이다. - 아무것도 사용할 요청이 없으면 현재 시간을 증가시켜준다.
풀이 방향
저는 먼저 시간으로 배열들을 정렬을 해줬습니다.
편하게 하기위해 Disk 라는 객체를 만들었습니다.
그후 반복문 while 을 이용해 반복시켰습니다.
현재 시간보다 작은 Disk를 뽑아 2번째 Queue에 담았습니다.
Queue 에 담긴 값중 작업의 소요시간이 가장 작은 값을 꺼내 요청으로 부터 작업종료 시간을 구해 answer에 다 더했습니다.
그후 jobs의 length 로 answer 를 나눠 평균을 구했습니다.
메인로직
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.PriorityQueue;
class Solution {
public int solution(int[][] jobs) {
int answer = 0;
PriorityQueue<Disk> sortWithIndex = new PriorityQueue();
PriorityQueue<Disk> priorityQueue2 = new PriorityQueue<>(this::compareToDelay);
List<Disk> answers = new ArrayList<>();
for (int[] job : jobs) {
sortWithIndex.add(new Disk(job[0], job[1]));
}
int time = 0;
while (!sortWithIndex.isEmpty()) {
while (!sortWithIndex.isEmpty() && sortWithIndex.peek().index <= time) {
priorityQueue2.add(sortWithIndex.poll());
}
if (!priorityQueue2.isEmpty()) {
Disk andDisk = priorityQueue2.poll();
answers.add(andDisk);
time += andDisk.delayTime;
answer += time - andDisk.index;
for (Disk disk : priorityQueue2) {
sortWithIndex.add(disk);
}
priorityQueue2.clear();
} else {
time ++;
}
}
int b = (int) Math.floor((answer / jobs.length));
return b;
}
public int compareToDelay(Disk o1, Disk o2) {
if (o1.delayTime > o2.delayTime) {
return 1;
} else if (o1.delayTime < o2.delayTime) {
return -1;
} else {
return 0;
}
}
Disk 클래스
class Disk implements Comparable<Disk> {
private int index;
private int delayTime;
public Disk(int index, int delayTime) {
this.index = index;
this.delayTime = delayTime;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Disk disk = (Disk) o;
return index == disk.index &&
delayTime == disk.delayTime;
}
@Override
public int hashCode() {
return Objects.hash(index, delayTime);
}
@Override
public int compareTo(Disk o) {
if (this.index > o.index) {
return 1;
} else if (this.index < o.index) {
return -1;
} else {
return 0;
}
}
@Override
public String toString() {
return "Disk{" +
"index=" + index +
", delayTime=" + delayTime +
'}';
}
}
}
느낀점
열심히 풀었는데 3개의 경우 빼고 다 시간초과가 났습니다.
원인 분석을 하다가 로직 구현을 잘못 접근해 발생 했다고 생각하고 다른 방식으로 풀어봤습니다.
하지만 또 시간초과가 발생해 다른사람들이 작성한 코드를 참고하여 풀어봤는데 마찬가지로 시간초과가 발생해 정말 힘들었습니다.
알고 봤더니 요청이 0보다 큰값으로 시작하는 경우가 전부 무한루프에 빠져 발생한 것이 었습니다.
while 문을 사용하면 당연히 무한루프를 염두해야 했는데 생각하지 못한것에 대해 많은 반성을 했습니다.
이번을 계기로 무한루프에 빠지는 실수는 안하게 될거 같습니다.