[백준 알고리즘/Kotlin] 1931번 회의실 배정 (feat. 입력 받기 이젠 정복한 듯...?)

 

1. 입력 받기

첫 줄에는 하나의 값 n을 받고, 둘째 줄부터 n+1 줄까지 공백을 사이에 둔 2개의 정수 받기

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))    
    
    val n = br.readLine().toInt()
    
    val meetings = mutableListOf<Pair<Int, Int>>()
    repeat(n) {
        val (start, end) = br.readLine.split(" ").map { it.toInt() }
        meetings.add(start to end)
    }
    
    br.close()
}

 

코드를 자세히 살펴보겠습니다.

1. mutableListOf
mutableListOf<Pair<Int, Int>>()는 Pair 클래스를 원소로 갖는 가변 리스트입니다.

그런데 가변 리스트라고요?
리스트는 기본적으로 불변한다는 성질을 가지고 있지만,
mutableListOf 함수를 사용하면 가변한 리스트를 생성할 수 있습니다.
(원소 추가 add / 제거 removeAt(i) / 변경 mutableList[i] = newValue 모두 가능)

2. Pair 클래스
Pair은 두 개의 값을 하나로 묶어 표현하는 기본 클래스입니다.
두 값은 first와 second라는 이름으로 접근할 수 있죠.

3. List와 Pair의 조합
- meetings 리스트는 각 회의의 시작시간과 끝나는 시간을 Pair로 묶어서 저장하는 것이 목적입니다.
  이는 각 회의의 정보를 하나의 단위로 표현하기 위함입니다.
- List<Pair<Int, Int>>라고 선언하면 됩니다.
  각 Pair는 하나의 회의를 나타내며, List는 모든 회의를 담는 자료구조로 사용되고 있죠.

4. to 함수
to는 두 값을 묶어서 Pair을 생성하는 코틀린의 표준 라이브러리 함수입니다.
A to B: A가 first에, B가 second에 할당

 

2. mutableListOf 오름차순 정렬하기

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))    
    
    val n = br.readLine().toInt()
    
    val meetings = mutableListOf<Pair<Int, Int>>()
    repeat(n) {
        val (start, end) = br.readLine.split(" ").map { it.toInt() }
        meetings.add(start to end)
    }
    meetins.sortedBy { it.first }
    
    br.close()
}

 

3. 기준 잡기

저는 계속 시작 시간이 빠른 순으로 정렬했습니다...

(자꾸 생각이 고착되네요. 여러 방면으로 생각하도록 시각을 넓혀야겠습니다.)

 

도저히 문제가 풀리지 않았는데요. 그러다, 시작 시간이 빠르면서 종료 시간도 빠른 순서로 정렬하였습니다.

(종료 시간이 빠른 순서라는 것이 더 큰 포인트입니다.)

[(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]

회의가 빨리 끝날수록 다음 회의를 빨리 시작함과 동시에,

더 많은 회의를 할 수 있기에 종료 시간을 기준으로 정렬했습니다.

 

4. 최종 코드

그 후, 반복문을 통해 각 회의에 대해 시작 시간이 현재까지의 종료 시간보다 크거나 같은 경우

해당 회의를 선택하고, 종료 시간을 업데이트하며 최대 회의의 수를 증가시킵니다.

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))    
    
    val n = br.readLine().toInt()
    
    val meetings = mutableListOf<Pair<Int, Int>>()
    repeat(n) {
        val (start, end) = br.readLine().split(" ").map { it.toInt() }
        meetings.add(start to end)
    }

    val sortedMeetings = meetings.sortedBy { it.first }.sortedBy { it.second }
    
    // 결과 : maxMeetingCnt, 최대 회의의 수
    var maxMeetingCnt = 0
    var endTime = 0
    
    for (meeting in sortedMeetings) {
        if (meeting.first >= endTime) {
            endTime = meeting.second
            maxMeetingCnt++
        }
    }
    
    println(maxMeetingCnt)
    br.close()
}

 

백준 문제 하단에 있는 알고리즘 분류도 잘 살펴봐야겠습니다. 그럼 아디다스...