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

진짜 하루종일 풀게된 문제

어떻게 풀어야 할지 고민하다가 처음 만든 답은

fun solution12(jobs: Array<IntArray>): Int {
        val playingQue = arrayListOf<Pair<Int, Int>>() // 요청시간 , 마지막 시간
        val waitingArray = mutableListOf<Pair<Int, Int>>() // 요청시간 , 걸리는 시간
        val endQue = arrayListOf<Pair<Int, Int>>()  // 요청시간, 끝나는 시간
        val descendingJobs = jobs.sortedBy { (start, _) -> start }
        var nowPosition = 0
        var timer = 0
        val defaultArray = descendingJobs.filter { it[0] == 0 } // 0초일때 요청되는 작업

        /** 우선 지금 들어갈 것들은 모두 waiting 에 넣어주고 난 뒤에 작업을 시작*/

        if (defaultArray.isNotEmpty()) {
            for (i in defaultArray) {
                waitingArray.add(descendingJobs[nowPosition][0] to descendingJobs[nowPosition][1]) // 무작위 웨이팅 어레이에 넣어줌
                nowPosition++  // 포지션 상승
            }
            playingQue.add(0, waitingArray[0].first to waitingArray[0].second)   // 플레잉 해줌
            waitingArray.sortBy { it.second }   // 웨이팅 정리해줌 소요시간이 작은것 부터
            waitingArray.removeAt(0)     // 하나 플레이 해줬으니 하나 삭제
        } //처음꺼 넣어주기
        timer++  // 1초로 변환

        while (endQue.size < jobs.size) {
            if (jobs.size - 1 >= nowPosition) { // 현재 더 들어갈 프로그램이 있다
                if (timer == jobs[nowPosition][0]) { // 이번 시간에 들어갈 요청되는 프로그램이 있다.
                    try {
                        if (playingQue.isEmpty()) {// 아무것도 재생중이지 않다   여러개중에 하나만 넣어준다.
                            val temporArray = descendingJobs.filter { it[0] == timer }.forEach {
                                waitingArray.add(it[0] to it[1])
                                nowPosition++
                            }
                            waitingArray.sortBy { it.second } // 정렬
                            playingQue.add(0, waitingArray[0].first to waitingArray[0].second + timer) // 플레이에 넣어줌
                            waitingArray.removeAt(0) // 제일 앞에거 삭제

                        } else {//현재 재생중인 메모리가 있다면 -> 웨이팅 어레이에 넣어줌
                            descendingJobs.filter { it[0] == timer }.forEach {
                                waitingArray.add(it[0] to it[1])
                                nowPosition++
                            }
                        }
                    } catch (e: Exception) {
                        return 0
                    }

                }
            }
            if (waitingArray.isNotEmpty() && playingQue.isEmpty()) { // 기다리는 파일이 있다 + 플레잉되는 파일이 없다.
                waitingArray.sortBy { it.second } // 정렬
                playingQue.add(0, waitingArray[0].first to timer + waitingArray[0].second) //지금 요청되는 아이를 넣어줌
                waitingArray.removeAt(0) // 웨이팅 하나를 지워주고
            }


            //공통 사항
            if (playingQue.isNotEmpty() && playingQue[0].second == timer + 1) {  // 재생중인 파일이 있는데 다음타임이 끝이다.
                endQue.add(playingQue[0])
                playingQue.clear()
            }

            timer++

        }


        var answer = endQue.fold(0) { acc, pair ->
            acc + pair.second - pair.first
        }
        val answerNext = answer.toDouble()
        val aa = floor(answerNext / jobs.size).toInt()

        return aa
    }

아무리 해도 답이 하나만 맞고 다 틀려서 이리보고 저리봐도 논리상 틀린거 없는거 같은데 계속 틀리거나 시간이 없다고 나옴...

그래서 생각한게 똑같은 논리에 queue를 써보자고 6시간이 지나서야 생각해봄

 

1. LinkedList 와 Array

 

측량에서 공부했었던 벡터와 성격과 비슷함

노드를 이용하여 만들어 졌기때문에 큰 어레이에서 구조변경이 용이함??.... 앞뒤의 자료구조만 바꾸면 되기 때문임

그리고 Array는 변경하기 위해서는 모든 데이터의 자리이동이 일어나기 때문에 좀더 느리다

하지만 검색을 할 경우 Array가 좀 더 빠르다고 한다.

 

그럼 내가 queue를 사용해서 푼 풀이

fun solution(jobs: Array<IntArray>): Int {
        val pQueue = LinkedList<Playing>() as Queue<Playing>
        val wQueue = PriorityQueue<Waiting>()
        val eQueue = LinkedList<Ended>() as Queue<Ended>
        var timer = 0
        while (eQueue.size < jobs.size) {
            /**이 시간에 요청되는 프로그램을 웨이팀에 넣는다*/
            jobs.filter { it[0] == timer }.forEach {
                wQueue.offer(Waiting(timer, it[1])) // 웨이팅에 넣기
            }

            /**
             * 플레이 되는게 없으면 웨이팅에서 젤 빠른거 하나 넣고 나머지는 웨이팅 기다리기
             * 안 비었다면 다음time 에 종료되는지 확인후 종료되면 equeue에 넣기
             * */
            if (pQueue.isEmpty() && wQueue.isNotEmpty()) {
                val item = wQueue.poll()
                pQueue.offer(Playing(item.apply, timer, item.needTime))
            }
            if (pQueue.peek() !=null &&pQueue.peek().let { it.startTime + it.needTime } == timer + 1) { // 담 타임에 끝남
                val item = pQueue.poll()
                eQueue.offer(Ended(timer + 1 - item.apply))
            }
            /**플레이 되는게 없으면 웨이팅에서 젤 빠른거 하나 넣고 나머지는 웨이팅 기다리기*/
            timer++ // 시간은 간다
        }
        val b = eQueue.fold(0) { acc, ended ->
            (acc + ended.forAnswer)
        }
        println(b)
        return b / eQueue.size

    }

    data class Waiting(var apply: Int, var needTime: Int) : Comparable<Waiting> {
        override fun compareTo(other: Waiting): Int {
            return this.needTime.compareTo(other.needTime)
        }
    }


    data class Playing(var apply: Int, var startTime: Int, var needTime: Int) : Comparable<Waiting> {
        override fun compareTo(other: Waiting): Int {
            return this.needTime.compareTo(other.needTime)
        }

    }

    data class Ended(var forAnswer: Int)

 

2. 항상 볼게 있는 다른사람의 풀이

class Solution {
    fun solution(jobs: Array<IntArray>): Int {
        var jobList = jobs.map { it[0] to it[1]}.sortedBy { it.first }
        var sortedTime: PriorityQueue<Pair<Int, Int>> = PriorityQueue(compareBy { it.second })
        var current = 0
        var sum = 0
        while (!jobList.isEmpty() || !sortedTime.isEmpty()) {
            val c = jobList.takeWhile { it.first <= current }
            sortedTime.addAll(c)
            jobList = jobList.drop(c.size)
            if (sortedTime.isEmpty()) {
                current = jobList.first().first
            } else {
                val j = sortedTime.poll()
                current += j.second
                sum += current - j.first
            }
        }

        return sum / jobs.size
    }
}

위에 처럼 

priorityqueue 에 compareby를 바로 넣어서 pair을 넣는 방법이 있군..

 

 

방식은 나랑 비슷한 것 같은데.. 명령어가 신기함

 

takewhile 

Returns a list containing first elements satisfying the given predicate.

필터를 써서 만드는것을 takewhile 명령어로 바로 리스트를 추출 가능

 

drop 

Returns a list containing all elements except first n elements.
Throws:
IllegalArgumentException - if n is negative

 

나는 계속 존재하는 변하지 않는 함수에 filter을 사용해서 좀 비효율 적인데

이렇게 drop으로 사용한 원소를 제거함으로 탐색범위 줄이고 시간 효율을 늘릴수 있다.

 

 

 

※ 제출 할때 런타임 에러 뜨던데 이건 내가 코드를 잘못 만든거고

시간 초과가 뜨면 비효율 적으로 만든거임