문제 설명
회의실 배정 문제는 주어진 시간 목록을 바탕으로 회의실을
효율적으로 배정하는 알고리즘 문제입니다. N개의 회의가 있고,
각각의 회의는 시작 시간과 끝 시간을 가진다고 가정합니다.
회의실은 동시에 하나의 회의만 진행할 수 있으며, 같은 시간에 진행
되는 회의가 있을 경우, 해당 회의는 배정할 수 없습니다.
따라서, 가능한 회의 수를 최대화하는 알고리즘을 작성하세요.
입력 형식
- 첫 번째 줄에 N (1 ≤ N ≤ 100,000)이 주어진다.
- 다음 N개의 줄에 각 회의의 시작 시간과 종료 시간이 주어진다.
- 시작 시간은 종료 시간보다 작으며, 모든 시간은 0에서 10^6 사이의 정수이다.
출력 형식
- 배정할 수 있는 최대 회의 수를 출력한다.
예제
입력 예제:
5
1 3
2 4
3 5
5 6
4 7
출력 예제:
4
문제 해결 과정
이 문제는 그리디 알고리즘을 사용하여 접근할 수 있습니다.
그리디 알고리즘은 최적의 해를 찾기 위해 매 단계에서 최적의 선택을
하는 방법론입니다. 회의실 배정 문제의 경우, 회의가 끝나는 시간을 기준으로
정렬하여 가능한 많은 회의를 배정하는 방법이 가장 효과적입니다.
1. 회의 정렬
회의의 종료 시간을 기준으로 정렬을 수행해야 합니다.
종료 시간이 빠른 회의부터 우선적으로 처리함으로써
나중에 시작되는 회의의 시작 시간을 사용하여 더 많은 회의를 배정할 수 있습니다.
예를 들어, 다음과 같은 회의 데이터가 있을 때:
1 3
2 4
3 5
5 6
4 7
이 데이터를 종료 시간 기준으로 정렬하면 다음과 같이 됩니다:
1 3
2 4
3 5
4 7
5 6
2. 가능 회의 계산
정렬된 회의 리스트를 바탕으로 각 회의를 순회하며
배정할 수 있는 회의를 계산합니다.
종료 시간이 가장 빠른 회의가 끝난 후에 시작할 수 있는
다음 회의를 확인하는 방식으로 진행합니다.
이를 위해 변수 lastEnd를 사용하여
마지막으로 배정한 회의의 종료 시간을 기록합니다.
각 회의를 순회하며 시작 시간이 lastEnd보다
크거나 같은 회의만 배정할 수 있습니다.
3. 코드 구현
다음 코드를 통해 위의 로직을 구현할 수 있습니다.
코틀린 코드를 아래와 같이 작성해보겠습니다.
fun maxMeetings(meetings: Array>): Int {
// 회의를 종료시간 기준으로 정렬
val sortedMeetings = meetings.sortedBy { it.second }
var count = 0
var lastEndTime = 0
for (meeting in sortedMeetings) {
// 회의 시작 시간이 마지막 회의 끝나는 시간보다 크거나 같으면 회의 배정
if (meeting.first >= lastEndTime) {
count++
lastEndTime = meeting.second
}
}
return count
}
fun main() {
val n = readLine()!!.toInt()
val meetings = Array(n) {
val input = readLine()!!.split(" ")
Pair(input[0].toInt(), input[1].toInt())
}
println(maxMeetings(meetings))
}
결론
이번 포스트에서는 코틀린을 사용하여 회의실 배정 문제를 해결해보았습니다.
그리디 알고리즘을 활용한 접근으로, 주어진 회의 데이터의 종료 시간을 기준으로 정렬하고,
각 회의의 시작 시간을 체크하여 최대한 많은 회의를 배정할 수 있었습니다.
이 문제는 효율적인 알고리즘으로 최적의 해를 구할 수 있는 그리디 알고리즘의
좋은 예시라고 할 수 있습니다.
이와 같은 논리와 접근 방식을 여러 문제에 적용하면
코딩 테스트에서 우수한 성과를 얻을 수 있습니다. 이제 여러분도
유사한 문제에 도전해보시길 바랍니다!