백준 2110번 공유기 설치 Kotlin 구현해보기

---

```

백준 2110번 공유기 설치 Kotlin 구현해 보기

```

Kimc Kotlin Study

이번 글을 통해 배워갈 내용

1.  백준 2110번 풀이

---

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

 

백준 2110번 공유기 설치는

난이도 골드 등급의 문제로서

 

N 개의 공유기를 H개의 집들 사이사이에 설치하고

H개의 직선 좌표가 주어질 때

가장 가까운 두 공유기 간의 거리에 최대치를 구해주면 되는 문제입니다.

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

집의 위치들을 정렬해 주고

거리를 가지고 이분탐색을 해서

특정 거리만큼의 거리를 두게 되면

주어진 공유기를 모두 설치할 수 있는지 확인을 해서

NlogN정도의 시간복잡도로 찾았습니다

 

fun main() {
    val inputDto = getInput()
    print(solution(inputDto))
}

fun getInput(): InputDto {
    val inputLine1 = readln().split(" ").map { k -> k.toInt() }
    val houseCnt = inputLine1[0]
    val routerCnt = inputLine1[1]
    val houseXPositions = IntArray(houseCnt)
    for (i in 0 until houseCnt) {
        houseXPositions[i] = readln().toInt()
    }
    return InputDto(houseCnt, routerCnt, houseXPositions)
}

data class InputDto(
    var houseCnt: Int,
    var routerCnt: Int,
    var houseXPositions: IntArray,
) {

    fun isRouterCountValid(mid: Int): Boolean {
        var lastHouseIdx = 0
        var curRouterCnt = 1

        for (idx in 1 until houseCnt) {
            if ((houseXPositions[idx] - houseXPositions[lastHouseIdx]) >= mid) {
                curRouterCnt++
                lastHouseIdx = idx
            }
        }
        return curRouterCnt < routerCnt
    }

    fun sortHouseXPositions() {
        houseXPositions.sort()
    }

    fun getHouseXPositionsMaxDistance(): Int {
        return (houseXPositions[houseXPositions.size - 1] - houseXPositions[0] + 1)
    }
}

fun solution(dto: InputDto): String {
    return findMaximumProximateDistance(dto)
}

fun findMaximumProximateDistance(
    dto: InputDto
): String {
    dto.sortHouseXPositions()
    return "${binarySearch(dto)}"
}

private fun binarySearch(dto: InputDto): Int {
    var left = 1
    var right = dto.getHouseXPositionsMaxDistance()
    while (left < right) {
        val mid = (left + right) / 2
        if (dto.isRouterCountValid(mid)) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return left - 1
}


// https://codemasterkimc.tistory.com/

 

테스트

import org.junit.jupiter.api.Assertions.assertEquals
import org.junit.jupiter.api.Test

internal class MainKtTest {

    @Test
    fun test() {
        assertEquals(
            "3",
            solution(
                InputDto(
                    5, 3,
                    intArrayOf(1, 2, 8, 4, 9)
                )
            )
        )
        assertEquals(
            "10",
            solution(
                InputDto(
                    2, 2,
                    intArrayOf(0, 10)
                )
            )
        )
        assertEquals(
            "20",
            solution(
                InputDto(
                    3, 2,
                    intArrayOf(0, 10, 20)
                )
            )
        )
        assertEquals(
            "3",
            solution(
                InputDto(
                    3, 3,
                    intArrayOf(0, 3, 7)
                )
            )
        )
    }
}

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---