[백준] 2170번: 선 긋기

문제링크

• 입력 x에 대해 오름차순으로 정렬합니다.
• 시작 정보(0번째 인덱스)를 저장하고, 1부터 (n-1)번째까지 순회합니다.
• 분리된 선인지 더 긴 선 정보가 있는지 확인하면서 길이를 누적해주고 길이 정보를 변경시켜줍니다.
• 분리된 선을 만났을 때에만 길이를 누적해주기 때문에 순회가 끝난 뒤에 잊지말고 반드시 길이를 누적해주어야 합니다.

var answer = 0

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val n = br.readLine().toInt()

    val lines = mutableListOf<Pair<Int, Int>>()
    for (i in 0 until n) {
        val (x, y) = br.readLine().split(" ").map { it.toInt() }
        lines.add(Pair(x, y))
    }
    lines.sortBy { it.first }
    val answer = lineSweepingStartWithOne(lines)
    bw.write("$answer")

    br.close()
    bw.close()
}

fun lineSweepingStartWithOne(lines: MutableList<Pair<Int, Int>>): Int {
    var start = lines[0].first
    var end = lines[0].second
    lines.drop(1).forEach { (x, y) ->
        if (isSeparateLine(x, end)) {
            accumulateLength(end - start)
            // new start position
            start = x
            end = y
        } else if (isLongerLine(y, end)) end = y
    }
    accumulateLength(end - start)
    return answer
}

fun isSeparateLine(x: Int, end: Int): Boolean {
    return x > end
}

fun accumulateLength(length: Int) {
    answer += length
}

fun isLongerLine(y: Int, end: Int): Boolean {
    return y > end
}

시간복잡도

O(n)