<백준> 공유기 설치(Gold 4)

[백준]

2110번: 공유기 설치

[깃허브]

ForCodeKata/baekjoon 문제집/공유기 설치 at main · heesoo-park/ForCodeKata

제출 결과

---

 

생각보다는 아주 간단한 개념이 들어가있는데 골드인 문제였다.

물론 이론적으로 간단한 개념이지 코드 구현으로는 나한테 어려운 개념이었다.

바로 '이분탐색'이다.

* 이진 탐색(이분 탐색) 알고리즘
  정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 알고리즘
  시간 복잡도 : O(logN)

 

그런데 어떻게 이 문제에서 어떤 걸 절반씩 나눌 수 있는지가 의문이었다.

범위가 꽉 채워져서 입력되는 것도 아니고 구해야하는 건 가장 인접한 두 공유기 사이의 최대 거리인데...

궁금증에 대한 답을 찾다가 보니 알게 된건 '공유기 최대 거리를 몇 이상으로 해야할까?'를 기준으로 삼아 둘로 나누는 거였다.

몇 이상이라고 한다면 몇 이상을 한 편에, 그 미만은 다른 편에 둘 수 있고 이는 이분탐색이 되는 것이다..!!(들어오는 값들이 균일한 범위를 가진 값이 아니기 때문에 정확히 절반을 말하는 것은 아니다.)

전혀 생각지 못한 나눔 방식이었다.

 

이렇게 나눠가며 진행을 할 때 몇 이상이 가능하다면 좀 더 큰 숫자에서도 가능한지 체크하고, 가능하지 않다면 좀 더 작은 숫자에서는 가능한지 체크한다.

그리고 조건에 맞는 값이 있었다면 이 값이 최대 거리인지 비교하여 값을 업데이트하면 된다.

 

이분 탐색을 하려면 리스트 내부의 데이터가 정렬되어있어야만 사용할 수 있기 때문에 탐색을 진행하기 전에 정렬을 해줬다.

 

점점 다양한 알고리즘들이 나타나고 있다.

어서 소화가...

 

해당 방법으로 작성한 코드는 다음과 같다.

import java.io.BufferedWriter
import java.io.OutputStreamWriter

val houses = mutableListOf<Int>()

fun main() = with(System.`in`.bufferedReader()) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    var result = 0

    val (n, c) = readln().split(' ').map { it.toInt() }
    repeat(n) {
        houses.add(readln().toInt())
    }

    houses.sort()

    var low = 1
    var high = houses[n - 1] - houses[0]
    while (low <= high) {
        val mid = (low + high) / 2

        var cnt = 1
        var prev = houses[0]
        for (i in 1 until n) {
            if (houses[i] - prev >= mid) {
                cnt++
                prev = houses[i]
            }
        }

        if (cnt >= c) {
            result = maxOf(result, mid)
            low = mid + 1
        } else {
            high = mid - 1
        }
    }

    bw.write("$result\n")
    bw.flush()
    bw.close()
}

 

참고)

https://jaimemin.tistory.com/966