[백준] 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)
Author And Source
이 문제에 관하여([백준] 2170번: 선 긋기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kldaji/백준-2170번-선-긋기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)