(프로그래머스) 디스크 컨트롤러

문제

https://programmers.co.kr/learn/courses/30/lessons/42627

접근

일단 최대한 비는 시간을 만들면 안되며 소요 시간이 가장 짧은 작업을 먼저 수행해야 한다고 생각했다. 요청 시간과 소요 시간 둘 다 정렬 기준이 될 수 있을 것이라고 생각해서 두 가지 기준을 모두 만들고 정렬한 후 처리하는 방식으로 접근하였다.

잘못된 코드

import java.util.*;

class Node {
    int start;
    int cost;
    
    Node(int start, int cost) {
        this.start = start;
        this.cost = cost;
    }
}

class Solution {
    Comparator<Node> c1 = new Comparator<Node>() {
        @Override
        public int compare(Node n1, Node n2) {
            if (n1.start > n2.start) {
                return 1;
            } else if (n1.start == n2.start) {
                if (n1.cost > n2.cost) {
                    return 1;
                }
                return -1;
            }
            return -1;
        }
    };
    
    
    Comparator<Node> c2 = new Comparator<Node>() {
        @Override
        public int compare(Node n1, Node n2) {
            if (n1.cost > n2.cost) {
                return 1;
            } else if (n1.cost == n2.cost) {
                if (n1.start > n2.start) {
                    return 1;
                }
                return -1;
            }
            return -1;
        }
    };
    
    public int solution(int[][] jobs) {
        List<Node> list = new ArrayList<>();
        for (int i = 0; i < jobs.length; i++) {
            list.add(new Node(jobs[i][0], jobs[i][1]));
        }
        
        Collections.sort(list, c1); // 시작 시간이 작은 순으로 정렬
        int answer1 = func(list);
        
        Collections.sort(list, c2); // 소요 시간이 작은 순으로 정렬
        int answer2 = func(list);
    
        int answer = Math.min(answer1, answer2);
        return answer;
    }
    
    int func(List<Node> list) {
        Node startNode = list.get(0);
        int sum = startNode.start + startNode.cost; // 지금까지 걸린 시간
        int answer = startNode.start + startNode.cost; // /size한게 정답
                
        for (int i = 1; i < list.size(); i++) {
            Node node = list.get(i);
            int start = node.start;
            int cost = node.cost;
            
            if (start > sum) {
	   // 이 조건문이 굉장히 잘못되었다...
                answer += (start + cost); 
                sum = start + cost;
            } else {
	   // 이 조건문은 맞지만 전체적인 접근이 틀렸다.
                answer += sum + cost - start;
                sum = sum + cost;
            }
        }
                                
        return answer / list.size();
    }
}

남은 작업에 따라 기준이 요청 시간이 되는지 소요 시간이 되는지 달라지게 된다. 하지만, 그 사항을 고려하지 않고 구현한 것이 가장 큰 잘못된 이유라고 생각한다.

정답 코드

import java.util.*;

class Node {
    int start;
    int cost;
    
    Node(int start, int cost) {
        this.start = start;
        this.cost = cost;
    }
}

class Solution {    
    Comparator<Node> c = new Comparator<Node>() {
        @Override
        public int compare(Node n1, Node n2) {
            if (n1.cost > n2.cost) {
                return 1;
            } else if (n1.cost == n2.cost) {
                if (n1.start > n2.start) {
                    return 1;
                }
                return -1;
            }
            return -1;
        }
    };
    
    public int solution(int[][] jobs) {
        List<Node> list = new ArrayList<>();
        for (int i = 0; i < jobs.length; i++) {
            list.add(new Node(jobs[i][0], jobs[i][1]));
        }
        
        Collections.sort(list, c); // 소요 시간이 작은 순으로 정렬
        int answer = func(list);
    
        return answer;
    }
    
    int func(List<Node> list) {
        List<Node> temp = new ArrayList<>();
        temp.addAll(list);
        int sum = 0;
        int answer = 0;
        int size = list.size();
        
        while (temp.size() > 0) {
            for (int i = 0; i < temp.size(); i++) {
                Node node = temp.get(i);
                int start = node.start;
                int cost = node.cost;
                
                if (start <= sum) {
                    answer += sum + cost - start;
                    sum = sum + cost;
                    temp.remove(i);
                    break;
                }
                
                if (i == temp.size() - 1) {
                    sum++;
                }
            }
        }
                                                
        return answer / size;
    }
}

처리할 작업을 만났을 때 하나씩 빼주었다. 또한, 현재까지 누적하여 실행된 시간보다 모든 작업의 요청 시간이 더 느릴 경우 누적 시간을 늘려주는 방향으로 바꾸었다.

요약

• 최대한 비는 작업 수행 시간을 만들면 안된다. (실행 시간이 같다면, 요청 시간이 가장 빠른 작업을 가져와야 한다.)
• 현재까지 누적된 시간보다 요청 시간이 더 빠르거나 같다면 무조건 실행 시간이 작은 작업을 빼와야 한다.