프로그래머스 - 야간 전술 보행(Kotlin)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/133501

 

[문제 설명]

감시 중인 경비원들이 있을 때, 어디까지 갈 수 있을까?

 

[접근 방법]

코앞에 있는 경비원만 신경 쓰면 된다.

우선 순위 큐로 화랑이가 앞으로 만날 경비병의 위치만 조심하면 된다.

경비병들은 서로 겹치는 곳을 감시하지 않으므로 성립하는 방법.

 

[내 답안 수정하기]

import java.util.PriorityQueue
// 야간 전술 보행
class Solution {
    fun solution(distance: Int, scope: Array<IntArray>, times: Array<IntArray>): Int {
        var currentLocation = 0
        val pq = PriorityQueue<Guard>()
        for (i in scope.indices) {
            pq.offer(Guard(range = intArrayOf(scope[i][0].coerceAtMost(scope[i][1]), scope[i][0].coerceAtLeast(scope[i][1])), time = times[i]))
        }

        while (currentLocation < distance) {
            currentLocation++
            // if : 이 앞에 감시 중인 경비원이 없으면. 끝까지 도착 가능하므로 distance 리턴
            if (pq.isEmpty()) {
                return distance
            }

            var nearestGuard = pq.peek()
            
            if (currentLocation > nearestGuard.range[1]) { // if : 경비병이 감시 중인 곳을 넘어갔으면, 우선순위 큐에서 poll을 통해 다음 경비병을 부른다.
                pq.poll()
                continue
            } else if (currentLocation < nearestGuard.range[0]) {   // else if : 가장 가까운 경비병이 더 뒤에 있으면 거기까지는 바로 이동 가능하므로
                현재 위치를 경비병의 감시 시작점으로 둔다.
                currentLocation = nearestGuard.range[0]
            }

            // if : 현재 경비병의 감시 범위 안에 있고 && 현재 시간이 감시중인 시간이면
            // 걸렸으므로 현재 위치 리턴
            if (currentLocation <= nearestGuard.range[1] &&
                currentLocation % (nearestGuard.time[0] + nearestGuard.time[1]) in 1..nearestGuard.time[0]
            ) {
                return currentLocation
            }
        }

        return currentLocation
    }

    // 시작점에 가장 가까운 순으로 경비를 정렬한다.
    class Guard(val range: IntArray, val time: IntArray): Comparable<Guard> {
        override fun compareTo(other: Guard): Int {
            return this.range[0].compareTo(other.range[0])
        }
    }
}