[백준] 1449번 수리공 항승(그리디)[Kotlin - 코틀린]

백준 1449번 문제입니다. (solved.ac) 기준 실버 3 문제입니다.

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

1449번: 수리공 항승

문제

문제 접근

첫 번째 줄에 물이 새는 곳의 개수, 테이프의 길이가 주어집니다.

두 번째 줄에는 물이 새는 곳이 주어지고, 물을 막을 땐 그 위치의 좌우 0.5만큼을 같이 막아주어야합니다.

테이프의 최소 개수를 구해야합니다.

예제 1번을 보면 테이프의 길이가 2이고 4개의 구멍을 막기 위하여 테이프가 총 2개가 필요합니다.

이는 1, 2를 한 테이프로 막고, 100, 101을 한 테이프로 막는 다는 소리인데
1을 막기위하며 0.5 - 1.5, 2를 막기 위하여 1.5 - 2.5를 막아야하는데 테이프의 길이가 2이기 때문에 한 테이프로 이를 막을 수 있습니다.

100, 101도 마찬가지.

물이 새는 곳의 정보(whereLeacked)를 오름차순으로 정렬한 후 forEachIndexed문을 사용하여 탐색합니다.

첫 번째 인덱스에서는 반드시 테이프를 붙여야합니다. lastLocation은 마지막으로 테이프를 붙인 위치가 담기게 될 것인데 좌, 우로 0.5만큼 더 붙여야 하기 때문에 -0.5f를 해줍니다.

마지막으로 테이프를 붙인 위치(lastLocation) + 테이프의 길이보다 현재 위치가 더 크다면 이전에 붙인 테이프로 현재 물이 새는 곳을 막을 수 없으므로 마지막 테이프를 붙인 위치를 갱신하고, 구멍을 막기위해 필요한 테이프의 개수를 1 증가시켜주었습니다.

정답 코드

fun main() {

    // 물이 새는 곳의 개수 n, 테이프의 길이 l
    val (n, l) = readln().split(" ").map { it.toInt() }

    // 누수된 곳 - 오름차순으로 정렬함.
    val whereLeaked = readln().split(" ").map { it.toInt() }.sorted()

    // 필요한 테이프의 개수
    var needTape = 0

    // 마지막으로 테이프를 붙인 위치
    var lastLocation = 0f

    // 누수된 곳을 forEachIndexed를 사용하여 순차 탐색.
    whereLeaked.forEachIndexed { index, location ->

        // 첫 번째(index == 0 일 때)에는 무조건 테이프를 붙여야함.
        // 테이프 붙임 처리.
        if (index == 0) {
            // 마지막으로 테이프를 붙인 위치는 테이프를 붙인 위치 - 0.5를 해줌.
            lastLocation = location - 0.5f
            // 필요한 테이프 1 증가.
            needTape++
            return@forEachIndexed
        }

        // 테이프 붙임처리
        if ((lastLocation + l) < location) {
            // 마지막으로 테이프를 붙인 위치는 테이프를 붙인 위치 - 0.5를 해줌.
            lastLocation = location - 0.5f
            // 필요한 테이프 1 증가.
            needTape++
        }

    }

    println(needTape)

}