[백준][코틀린][2109] 순회강연

https://www.acmicpc.net/problem/2109

2109번: 순회강연

문제 풀이

1. 입력으로 주어지는 강연 정보를 list 에 저장한다.

2. list 를 강연료를 기준으로 내림 차순 정렬한다.

3. 10001 크기의 lecture int 배열을 선언한다. 강연을 잡을 경우 lecture 배열에 강연료를 업데이트하는 용도로 사용한다.

4. list 를 다음과 같은 기준으로 탐색 한다.

4-1. list 의 d 값을 index 로 하여 lecture[index] 가 0일 경우에는 강연이 없는 날이므로 강연료(list.p) 를 lecture 배열에 업데이트 한다.

4-2. list 의 d 값을 index 로 하여 lecture[index] 가 0이 아닐 경우 강연이 이미 잡혀 있는 날이므로 이전 날짜를 탐색하여 lecture 배열에서 비어있는 부분 혹은 현재 강연료보다 싼 강연료를 탐색한다.

5. lecture 배열을 탐색하여 0이 아닌 값을 result 에 합하여 결과를 출력한다.

코드

import java.io.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    val list = mutableListOf<Lecture>()

    repeat(n) {
        val (p, d) = br.readLine().split(" ").map { it.toInt() }
        list.add(Lecture(p, d))
    }

    // 강연료 기준으로 내림차순 정렬 한다.
    list.sortWith { o1, o2 ->
        o2.p - o1.p
    }

    val lecture = IntArray(10001) { 0 }

    // list 를 탐색한다.
    for (l in list) {
        // lecture 배열의 list 의 d를 index 로 했을 때 값이 0이면 강연 스케쥴이 비어 있으므로 강연을 할 수 있다.
        if (lecture[l.d] == 0) {
            lecture[l.d] = l.p
        } else {
            // lecture 배열의 list 의 d를 index 로 했을 때 값이 0이 아니면
            // 이미 다른 강연 스케쥴이 있으므로 잡혀있는 강연 스케쥴보다 강연료가 비싼지 확인하여
            // 비싸면 현재 값으로 업데이트 한다.
            // 비싸지 않으면 이전 날짜를 탐색하여 비어있는 날짜 혹은 강연료가 현재 강연료 보다 싼 강연을 탐색한다.
            if (lecture[l.d] < l.p) {
                lecture[l.d] = l.p
            } else {
                var day = l.d - 1
                while (day > 0) {
                    if (lecture[day] == 0) {
                        lecture[day] = l.p
                        break
                    } else {
                        if (lecture[day] < l.p) {
                            lecture[day] = l.p
                            break
                        } else {
                            day--
                        }
                    }
                }
            }
        }
    }

    var result = 0

    for (lec in lecture) {
        if (lec != 0) result += lec
    }

    println(result)
}

private data class Lecture(val p: Int, val d: Int)