ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 프로그래머스 - 디스크 컨트롤러
    알고리즘 문제 풀이 2020. 10. 28. 23:11
    package programmers.heap
    
    /*
     * 2020-10-28
     * https://programmers.co.kr/learn/courses/30/lessons/42627
     */
    
    import java.util.*
    
    class DiskController {
        fun solution(jobs: Array<IntArray>): Int {
            // 입력 배열 정렬
            val jobQueue = PriorityQueue<IntArray> { o1, o2 ->
                when {
                    o1[0] > o2[0] -> 1
                    o1[0] < o2[0] -> -1
                    else -> o1[1].compareTo(o2[1])
                }
            }
    
            jobs.forEach {
                jobQueue.add(it)
            }
    
            val queue = PriorityQueue<IntArray> { o1, o2 ->
                o1[1].compareTo(o2[1])
            }
    
            // 총 사용 시간
            var answer = 0
    
            val job = jobQueue.poll()
            queue.add(job)
    
            // 현재 작업 진행 시간
            var jobTime = job[0]
    
            while (queue.isNotEmpty()) {
                val nowJob = queue.poll()
                jobTime += nowJob[1]
    
                answer += if (jobTime < nowJob[0]) {
                    nowJob[1]
                } else {
                    jobTime - nowJob[0]
                }
    
                // 현재 작업 시간 전에 들어온 작업들을 우선 순위 큐에 넣음
                while (jobQueue.peek() != null && jobQueue.peek()[0] < jobTime) {
                    val nextJob = jobQueue.poll()
                    queue.add(nextJob)
                }
    
                // 작업 큐가 비면 추가적으로 작업을 넣음
                if(queue.isEmpty() && jobQueue.peek() != null && jobQueue.peek()[0] >= jobTime){
                    val nextJob = jobQueue.poll()
                    queue.add(nextJob)
                    jobTime = nextJob[0]
                }
            }
            return answer / jobs.count()
        }
    }

    테스트 (자바로 작성)

    class heapTest {
        private static Stream<Arguments> diskControllerArgs() {
            return Stream.of(
                    arguments(9, new int[][]{{0, 3}, {1, 9}, {2, 6}}),
                    arguments(9, new int[][]{{1, 10}, {3, 3}, {10, 3}}),
                    arguments(15, new int[][]{{0, 10}, {4, 10}, {5, 11}, {15, 2}}),
                    arguments(10, new int[][]{{0, 10}}),
                    arguments(9, new int[][]{{0, 3}, {1, 9}, {2, 6}, {4, 3}}),
                    arguments(3, new int[][]{{0, 1}, {1, 2}, {500, 6}}),
                    arguments(6, new int[][]{{0, 3}, {1, 9}, {500, 6}}),
                    arguments(1, new int[][]{{0, 1}, {0, 1}, {1, 0}}),
                    arguments(3, new int[][]{{0, 3}, {4, 3}, {8, 3}}),
                    arguments(3, new int[][]{{0, 3}, {4, 3}, {10, 3}}),
                    arguments(3, new int[][]{{0, 5}, {6, 2}, {6, 1}}),
                    arguments(3, new int[][]{{0, 5}, {6, 1}, {6, 2}}),
                    arguments(5, new int[][]{{0, 5}, {2, 2}, {5, 3}}),
                    arguments(5, new int[][]{{0, 5}, {2, 2}, {4, 2}}),
                    arguments(4, new int[][]{{0, 3}, {0, 1}, {4, 7}}),
                    arguments(3, new int[][]{{0, 2}, {3, 6}, {3, 1}}),
                    arguments(6, new int[][]{{0, 5}, {1, 2}, {5, 5}}),
                    arguments(13, new int[][]{{0, 9}, {0, 4}, {0, 5}, {0, 7}, {0, 3}}),
                    arguments(72, new int[][]{{24, 10}, {28, 39}, {43, 20}, {37, 5}, {47, 22}, {20, 47}, {15, 2}, {15, 34}, {35, 43}, {26, 1}}),
                    arguments(72, new int[][]{{24, 10}, {28, 39}, {43, 20}, {37, 5}, {47, 22}, {20, 47}, {15, 34}, {15, 2}, {35, 43}, {26, 1}}),
                    arguments(13, new int[][]{{1, 9}, {1, 4}, {1, 5}, {1, 7}, {1, 3}})
            );
        }
    
        @ParameterizedTest
        @MethodSource("diskControllerArgs")
        public void diskControllerTest(int result, int[][] jobs) {
            assertEquals(result, new DiskController().solution(jobs));
        }
    }

    문제가 너무 애매한 부분이 있어서 푸는데 정말 오랜 시간이 걸렸다 ㅜㅜ

    반응형

    댓글 0

Designed by Tistory.