코틀린 코딩테스트 강좌, 선분을 그룹으로 나누기

문제 설명

선분의 집합이 주어졌을 때, 서로 겹치지 않도록 선분을 그룹으로 나누는 문제입니다.
각 선분은 시작점과 끝점으로 정의됩니다. 선분들 사이에 겹치는 부분이 있으면 같은 그룹에 속해야 하며,
겹치지 않는 선분들은 다른 그룹에 속해야 합니다.

입력

첫 번째 줄에는 선분의 개수 N (1 ≤ N ≤ 100,000)이 주어집니다.
두 번째 줄부터 N개의 줄에 각각의 선분의 시작점 l과 끝점 r (l <= r)이 주어집니다.

출력

총 필요한 그룹의 수를 출력합니다.

예제 입력

예제 출력

설명

주어진 선분들을 보면, 첫 번째와 두 번째 선분은 겹치므로 같은 그룹에 속합니다.
세 번째와 네 번째 선분도 겹치므로 둘은 같은 그룹에 속하고,
마지막 선분은 다른 그룹에 속하므로 총 3개의 그룹이 필요합니다.

해결 방법

이 문제를 해결하기 위해 올바른 접근 방식은 선분을 정렬한 후,
서로 겹치는 선분을 순차적으로 비교하여 그룹을 생성하는 것입니다.
다음과 같은 단계로 문제를 해결할 수 있습니다.

1단계: 입력 받기

선분을 리스트로 입력받습니다. 각 선분은 쌍으로 이루어져 있으므로
Pair 클래스를 사용하여 선분을 저장합니다.

2단계: 선분 정렬

선분들을 정렬하는 기준은 시작점입니다.
시작점이 작은 순서로 정렬한 후, 만약 시작점이 같다면 끝점이 짧은 것이 먼저 오도록 정렬합니다.

3단계: 그룹화

정렬된 리스트를 순회하면서 현재 그룹의 마지막 선분과 겹치는지 확인합니다.
겹치면 같은 그룹에 속하게 되고, 겹치지 않으면 새로운 그룹을 시작합니다.

4단계: 결과 출력

최종적으로 그룹의 수를 세어 출력합니다.

코드 예시 (Kotlin)

        data class Segment(val start: Int, val end: Int)

        fun countGroups(segments: List): Int {
            val sortedSegments = segments.sortedWith(compareBy({ it.start }, { it.end }))
            var groupCount = 0
            var maxEnd = -1

            for (segment in sortedSegments) {
                if (segment.start > maxEnd) {
                    groupCount++
                    maxEnd = segment.end
                } else {
                    maxEnd = maxOf(maxEnd, segment.end)
                }
            }
            return groupCount
        }

        fun main() {
            val n = readLine()!!.toInt()
            val segments = List(n) {
                val (l, r) = readLine()!!.split(" ").map { it.toInt() }
                Segment(l, r)
            }
            println(countGroups(segments))
        }

결론

이 문제를 통해 선분의 그룹화 문제를 해결하는 방법을 배웠습니다.
정렬과 리스트 순회를 통해 효과적으로 그룹의 수를 구할 수 있습니다.
코틀린을 활용하여 작성한 코드 구조는 재사용성이 높고 이해하기 쉬운 형태로
작성할 수 있었음을 확인했습니다.
코딩테스트에 있어서 선분 문제는 자주 출제되는 유형이므로,
이와 유사한 문제들을 연습해보는 것이 좋습니다.