[프로그래머스>LV3] 외벽점검(Kotlin)

프로그래머스

 

1. 문제

빠른 공사 진행을 위해 점검 시간을 1시간으로 제한했습니다.

친구들이 1시간 동안 이동할 수 있는 거리는 제각각이기 때문에, 최소한의 친구들을 투입해 취약 지점을 점검하고 나머지 친그들은 내부 공사를 돕도록 하려고 합니다.

 

[입력]

• 외벽의 길이 n
• 취약 지점의 위치가 담긴 배열 weak
• 각 친구가 1시간 동안 이동할 수 있는 거리가 담긴 배열 dist

[결과]

취약 지점을 점검하기 위해 보내야 하는 친구 수의 최솟값을 return

 

2. 풀이

문제를 먼저 보고 어떻게 풀어야 할까 고민을 오래한 문제가 아닐까 합니다. 😭

🌹 결론은 완전탐색으로 모든 경우를 확인해주면 풀 수 있는 문제입니다.ㅎㅎ

 

모든 경우를 탐색하기 위해서 처음으로 필요한 사항은 친구들을 투입하는 순서가 정해져 있지 않기 때문에

친구들을 투입할 수 있는 모든 가능한 순서들을 먼저 찾아낼 필요가 있습니다.

 

Python이었다면 라이브러리를 사용하면 되었지만, kotlin에서는 찾지 못해 결국 직접 구현하게 되었어요.😭

private fun <T> List<T>.permutations(k: Int): List<List<T>> {
    val result = mutableListOf<List<T>>()
    fun solve(k: Int, acc: MutableList<T>, visited: BooleanArray) {
        if (k == 0) {
            result.add(acc.toList())
            return
        }
        for ((index, i) in this.withIndex()) {
            if (visited[index].not()) {
                visited[index] = true
                acc.add(i)
                solve(k-1, acc, visited)
                acc.removeLast()
                visited[index] = false
            }
        }
    }

    val n = this.size
    solve(k, mutableListOf(), BooleanArray(n))
    return result.toList()
}

 

실제 사용하는 쪽에서는 간단하게 사용할 수 있도록 몇 개의 원소로 순열을 만들지 결정하는 k 값만 전달하면 되도록

메서드를 정의하였습니다. 🤗👍🏻

 

위 메서드를 사용해, 투입순서 배열은 👇🏻아래와 같이 받아올 수 있습니다.

val friendsNum = dist.size
val distPermu = dist.toList().permutations(friendsNum)

 

그 다음은 취약지점을 나타내는 weak 배열을 가공해 주어야 합니다.

🌹 외벽이 원형이기 때문에 마지막 지점에서 다시 처음지점까지 이동할 수 있도록 배열을 확장하는 방식으로 구현하였습니다.

val weakNum = weak.size
// 마지막 지점과 첫 지점을 다시 연결하도록 처리
val fullWeak = (weak + weak.map { it + n }).toList()

 

이제 이 fullWeak 배열을 이용해, 각 취약지점을 시작으로 하는 경우에서 친구들을 투입해 점검을 진행할 때,

몇 명의 친구가 필요한지 계산하여 최소값을 구하면 됩니다.🔥

 

그 외의 로직은 코드에 주석으로 적어두었습니다.

3. 코드

Kotlin

import kotlin.math.min

class Solution {
    fun solution(n: Int, weak: IntArray, dist: IntArray): Int {
        val friendsNum = dist.size
        val distPermu = dist.toList().permutations(friendsNum)
        
        var answer = friendsNum + 1

        val weakNum = weak.size
        val fullWeak = (weak + weak.map { it + n }).toList()
        // 각 취약지점을 시작점으로 지정해서 점검을 시작
        for (i in 0 until weakNum) {
            val repairs = fullWeak.subList(i, i + weakNum)
            // 모든 투입 가능한 순서를 탐색
            for (friend in distPermu) {
                var result = 1 // 투입한 친구의 수
                var friendIndex = 0 // 현재 투입중인 친구의 index
                // 현재 투입중인 친구의 위치
                var currentPos = repairs.first() + friend[friendIndex]
                
                // 취약지점을 순차적으로 점검할 수 있는지 검사
                for (z in 1 until weakNum) {
                    // 현재 투입중인 친구로는 해당 취약지점까지 이동할 수 없는 경우
                    if (repairs[z] > currentPos) {
                        // 새로운 친구 추가
                        result++
                        friendIndex++
                        // 더이상 투입할 수 있는 친구가 없는 경우
                        if (friendIndex >= friendsNum) break
                        // 투입중인 친구의 위치 변경
                        currentPos = repairs[z] + friend[friendIndex]
                    }
                }
                answer = min(answer, result)
            }
        }
        
        if (answer > friendsNum) return -1
        return answer
    }
    
    private fun <T> List<T>.permutations(k: Int): List<List<T>> {
        val result = mutableListOf<List<T>>()
        fun solve(k: Int, acc: MutableList<T>, visited: BooleanArray) {
            if (k == 0) {
                result.add(acc.toList())
                return
            }
            for ((index, i) in this.withIndex()) {
                if (visited[index].not()) {
                    visited[index] = true
                    acc.add(i)
                    solve(k-1, acc, visited)
                    acc.removeLast()
                    visited[index] = false
                }
            }
        }

        val n = this.size
        solve(k, mutableListOf(), BooleanArray(n))
        return result.toList()
    }
}