[프로그래머스][2019 카카오 개발자 겨울 인턴십][Kotlion] 징검다리 건너기

import java.util.PriorityQueue
import kotlin.math.min

data class Stones (
    val idx: Int,
    val vlu: Int
    )

class Solution {
    fun solution(stones: IntArray, k: Int): Int {
        var answer = 0
        var pq = PriorityQueue<Stones> { o1, o2 -> o2.vlu.compareTo(o1.vlu) }

        for(i in 1 .. k){
            pq.add(Stones(i-1,stones[i-1]))
        }
        answer = pq.peek().vlu

        var checkIndex = k
        while(checkIndex < stones.size){
            pq.add(Stones(checkIndex,stones[checkIndex]))
            checkIndex++
            while(pq.peek().idx < checkIndex - k){
                pq.poll()
            }
            answer = min(answer,pq.peek().vlu)

        }

        return answer
    }
}

해당 문제의 주요 포인트는

단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.

해당 문구 입니다. 아무리 해도 최적의 경우가 나올 수 없으며 1가지의 경우만 나온다는 것을 알 수 있습니다.

 

그리고 과정과 결과 값을 유추 해봤을때 k만큼의 길이를 비교하면서 해당 값의 최대값들을 비교하여 그 중 최소값을 찾으면 다리를 건널 수 있는 친구들의 수를 찾을 수 있다는 점을 확인할 수 있었습니다.

 

그렇다면 우선순위 큐에 내림차순으로  stones[i]의 값과 인덱스 i 값을 같이 저장한 후 최대값들을 비교하여 최소값을 찾아내고 진행됨에 따라 해당 자료의 맨 앞값(tones[i]의 값)dml 인덱스가 i-k보다 작을 경우 최대값들과 비교하지 않고 그냥 내보내는 조건을 만들어 준다면 k길이 만큼 비교하여 i-k ~ i 의 인덱스 중 가장 높을 값을 찾아 낼 수 있음을 확인 할 수 있습니다.

 

아직 저의 실력이 부족하여 설명이 많이 부족하지만 추후 더욱 공부하여 추가 설명을 할 수 있도록 하겠습니다.

하기는 해당 코드의 실행 결과 입니다.

 

정확성 테스트

테스트 1 〉	통과 (3.47ms, 61.8MB)
테스트 2 〉	통과 (3.61ms, 61.3MB)
테스트 3 〉	통과 (2.94ms, 61.2MB)
테스트 4 〉	통과 (4.28ms, 61.8MB)
테스트 5 〉	통과 (4.61ms, 60.3MB)
테스트 6 〉	통과 (5.05ms, 61.6MB)
테스트 7 〉	통과 (7.14ms, 60.2MB)
테스트 8 〉	통과 (5.97ms, 59.5MB)
테스트 9 〉	통과 (5.62ms, 61MB)
테스트 10 〉	통과 (4.67ms, 59.8MB)
테스트 11 〉	통과 (3.84ms, 59.9MB)
테스트 12 〉	통과 (3.47ms, 59.6MB)
테스트 13 〉	통과 (3.58ms, 61.5MB)
테스트 14 〉	통과 (5.19ms, 60.5MB)
테스트 15 〉	통과 (4.58ms, 60.1MB)
테스트 16 〉	통과 (5.26ms, 59.6MB)
테스트 17 〉	통과 (4.20ms, 58.7MB)
테스트 18 〉	통과 (3.44ms, 61.4MB)
테스트 19 〉	통과 (3.03ms, 62.8MB)
테스트 20 〉	통과 (3.57ms, 60.6MB)
테스트 21 〉	통과 (5.62ms, 61.3MB)
테스트 22 〉	통과 (4.43ms, 60.8MB)
테스트 23 〉	통과 (4.44ms, 60.8MB)
테스트 24 〉	통과 (3.61ms, 60.7MB)
테스트 25 〉	통과 (3.15ms, 60.5MB)

효율성 테스트

테스트 1 〉	통과 (52.96ms, 74.2MB)
테스트 2 〉	통과 (55.66ms, 74.4MB)
테스트 3 〉	통과 (48.67ms, 74.3MB)
테스트 4 〉	통과 (91.90ms, 71.8MB)
테스트 5 〉	통과 (91.56ms, 72.7MB)
테스트 6 〉	통과 (93.25ms, 74.7MB)
테스트 7 〉	통과 (44.06ms, 74MB)
테스트 8 〉	통과 (38.90ms, 74.1MB)
테스트 9 〉	통과 (48.25ms, 74.4MB)
테스트 10 〉	통과 (42.77ms, 75.7MB)
테스트 11 〉	통과 (40.74ms, 74MB)
테스트 12 〉	통과 (36.59ms, 73.9MB)
테스트 13 〉	통과 (80.76ms, 72.4MB)
테스트 14 〉	통과 (67.01ms, 73.9MB)