21942번: 부품 대여장

문제 출처 : https://www.acmicpc.net/problem/21942

 

언어 : Kotlin

 

문제 설명 :

송훈이는 로봇 동아리 회원이다. 로봇 동아리에서 필요한 부품이 있을 경우 자유롭게 빌려서 쓰고 다시 돌려놓으면 된다.

하지만 부품 정리를 하다가 부품 관리가 너무 힘들어져 새로운 시스템을 도입하려고 한다.

부품을 빌려갈 경우 부품 대여장에 정보를 반드시 작성해야한다. 또한 빌려간 부품을 반납 할 경우에도 부품 대여장에 정보를 작성해야한다.

또한 대여기간을 정하고 대여기간을 넘길 경우 1분당 벌금을 부여하도록 하는 시스템이다.

만약 대여기간이 5분, 1분당 벌금이 5원이라 했을 때 대여한 시각이 2021년 1월 1일 1시 5분이라면 2021년 1월 1일 1시 10분까지 반납해야한다.

2021년 1월 1일 1시 14분에 반납을 했다면 4분 늦었기 때문에 벌금을 20원을 내야한다.

 

부품 대여장에 쓰는 형식은 아래와 같다.

yyyy-MM-dd hh:mm [부품 이름] [동아리 회원 닉네임]

 

아래는 예시를 위한 부품 대여장에 작성된 정보이다. 대여기간이 5분, 벌금은 1원이라 가정하자.

2021-01-01 09:12 arduino tony9402
2021-01-01 09:13 monitor chansol
2021-01-01 09:18 arduino tony9402
2021-01-01 09:18 monitor chansol

 

위의 정보를 정리하면 아래와 같다.

tony9402가 2021년 1월 1일 오전 9시 12분에 arduino를 빌렸다.
chansol이 2021년 1월 1일 오전 9시 13분에 monitor를 빌렸다.
tony9402가 2021년 1월 1일 오전 9시 18분에 arduino를 반납했다.
chansol이 2021년 1월 1일 오전 9시 18분에 monitor를 반납했다.

 

tony9402는 1분 늦게 반납했기 때문에 벌금 1원을 내야한다.

부품을 대여할 때 지켜야 하는 조건이 있다.

1. 한 사람이 같은 종류의 부품을 두개 이상 대여하고 있는 상태일 수 없다.
2. 한 사람이 같은 시각에 서로 다른 종류의 부품들을 대여하는 것이 가능하다.
3. 같은 사람이더라도, 대여 기간은 부품마다 별도로 적용된다.

 

입력 :

첫 번째 줄에 부품 대여장에 작성된 정보의 개수 N, 대여기간 L, 벌금 F이 공백으로 구분되어 주어진다.

대여기간 형식은 DDD/hh:mm으로 DDD는 일, hh는 시간, mm은 분을 의미한다. (000/00:00 는 주어지지 않는다.)

두 번째 줄부터 N+1번째 줄까지 시간순으로 부품 대여장에 작성한 정보 (시각, 부품 이름 P, 회원 닉네임 M)이 공백으로 구분되어 주어진다.

빌린 시각의 형식은 yyyy-MM-dd hh:mm으로 yyyy는 연도, MM는 월, dd는 일, hh는 시간, mm는 분을 의미한다. 이 문제에서 들어오는 연도는 항상 2021년도이다.

부품 이름 P는 알파벳 소문자로만 이루어져 있다. 즉, 부품 이름에 공백이 없다.

회원 닉네임 M은 알파벳 소문자와 숫자(0 ~ 9)로만 이루어져있다. 즉, 회원 닉네임에 공백이 없다.

 

출력 :

벌금을 내야하는 사람들을 사전순으로 동아리 회원 닉네임 M와 내야하는 벌금을 한 줄씩 출력한다.
만약 벌금을 내야하는 사람들이 없는 경우는 -1을 출력한다.

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 512MB
•  2 ≤ N ≤ 80,000, N은 짝수
•  0 ≤ DDD ≤ 200
•  1 ≤ MM ≤ 12
•  0 ≤ hh ≤ 23
•  0 ≤ mm ≤ 59
•  1 ≤ F ≤ 4,000
•  5 ≤ |P|, |M| ≤ 20
• 부품을 반납하지 않은 사람은 없다.

 

입출력 예 :

입력	출력
8 014/00:00 5 2021-01-01 09:12 arduino tony9402 2021-01-13 13:24 arduino tony9402 2021-01-23 14:04 raspberrypi tony9402 2021-02-01 18:21 resistance amsminn 2021-02-03 23:14 transistor codethinking 2021-02-08 22:14 transistor codethinking 2021-02-09 12:45 resistance amsminn 2021-02-13 14:37 raspberrypi tony9402	tony9402 50565
4 015/00:00 5 2021-01-01 09:12 arduino tony9402 2021-01-13 13:24 arduino tony9402 2021-02-15 12:12 raspberrypi q540jh 2021-02-15 12:13 raspberrypi q540jh	-1
4 000/00:05 1 2021-01-01 09:12 arduino tony9402 2021-01-01 09:13 monitor chansol 2021-01-01 09:18 arduino tony9402 2021-01-01 09:18 monitor chansol	tony9402 1

 

풀이 : 

import java.io.BufferedWriter
import java.io.OutputStreamWriter
import java.time.LocalDate
import java.time.format.DateTimeFormatter
import java.time.temporal.ChronoUnit
import kotlin.math.abs

data class Info(val dateTime: Long, val p: String, val m: String)

const val BASE = 100000

fun main() = with(System.`in`.bufferedReader()) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val (n, l, f) = readLine().split(" ")
    val infoList = MutableList(n.toInt()) {
        val cur = readLine().split(" ")
        Info(dateTimeToNum(cur[0], cur[1]), cur[2], cur[3])
    }

    val rentalPeriod = rentalPeriodToNum(l)
    val fineList = mutableMapOf<String, Long>()

    val group = infoList.groupBy { it.m }
    group.forEach { (t, u) ->
        val list = u.sortedWith(compareBy<Info> { it.p }.thenBy { it.m }.thenBy { it.dateTime })
        var index = list.lastIndex

        while (index >= 0) {
            val curRental = list[index]
            val curReturn = list[index - 1]

            val diff = curRental.dateTime - curReturn.dateTime

            if (diff > rentalPeriod) {
                val date = computeDateToTime(curRental.dateTime / BASE, curReturn.dateTime / BASE)
                val time = curRental.dateTime % BASE - curReturn.dateTime % BASE

                val delayedPeriod = date - (rentalPeriod / BASE)
                val delayedTime = time - (rentalPeriod % BASE)
                val fineTotal = ((delayedPeriod * 24 * 60) + delayedTime) * f.toInt()

                if (fineList.containsKey(t)) {
                    fineList[t] = fineList[t]!! + fineTotal
                } else {
                    fineList[t] = fineTotal
                }
            }

            index -= 2
        }
    }

    if (fineList.isEmpty()) {
        bw.write("-1")
    } else {
        fineList.toSortedMap().forEach { (t, u) ->
            bw.write("$t $u\n")
        }
    }

    bw.flush()
    bw.close()
}

fun dateTimeToNum(date: String, time: String): Long {
    val newDate = date.replace("-", "").toLong() * BASE
    val newTime = time.split(":").map { it.toInt() }.let { it[0] * 60 + it[1] }

    return newDate + newTime
}

fun rentalPeriodToNum(l: String): Int {
    val newL = l.split("/")
    val date = newL[0].toInt() * BASE
    val time =  newL[1].split(":").map { it.toInt() }.also { it[0] * 60 + it[1] }.sum()

    return date + time
}

fun computeDateToTime(date1: Long, date2: Long): Long {
    val formatter = DateTimeFormatter.ofPattern("yyyyMMdd")

    val newDate1 = LocalDate.parse(date1.toString(), formatter)
    val newDate2 = LocalDate.parse(date2.toString(), formatter)

    return abs(ChronoUnit.DAYS.between(newDate1, newDate2))
}

 

위는 기존에 풀었던 방식인데, 지속적인 출력초과를 잡지 못해 아래의 풀이를 참고하여 다시 작성한 코드가 아래의 코드이다.

 

 

https://comdolidol-i.tistory.com/m/278

[c++][백준 21942][해시/파싱] 부품 대여장 - 컴도리돌이

 

import java.io.BufferedWriter
import java.io.OutputStreamWriter

val month = arrayOf(0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)

data class Info(val mm: String, val dd: String, val time: String, val obj: String, val name: String, val flag: Boolean)

fun main() = with(System.`in`.bufferedReader()) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val (n, l, f) = readLine().split(" ")
    val reservedTime = toMinutes(l)

    val objInfo = mutableMapOf<String, Info>()
    val peopleFee = mutableMapOf<String, Long>()

    repeat(n.toInt()) {
        val (date, time, obj, name) = readLine().split(" ")

        val mm = date.substring(5, 7)
        val dd = date.substring(8, 10)

        val key = obj + name
        if (objInfo[key]?.flag == true) {
            val info = objInfo[key]!!
            val used = feeCal(info.mm, info.dd, info.time, mm, dd, time)
            if (reservedTime < used) {
                peopleFee[name] = peopleFee.getOrDefault(name, 0L) + (used - reservedTime) * f.toLong()
            }
            objInfo.remove(key)
        } else {
            objInfo[key] = Info(mm, dd, time, obj, name, true)
        }
    }

    if (peopleFee.isEmpty()) {
        bw.write("-1")
    } else {
        val sortedPeopleFee = peopleFee.toList().sortedBy { it.first }
        for ((person, fee) in sortedPeopleFee) {
            bw.write("$person $fee\n")
        }
    }

    bw.flush()
    bw.close()
}

fun toMinutes(timeStr: String): Long {
    val day = timeStr.substring(0, 3).toLong()
    val hour = timeStr.substring(4, 6).toLong()
    val min = timeStr.substring(7, 9).toLong()
    return (day * 24 + hour) * 60 + min
}

fun feeCal(m: String, d: String, t: String, mm: String, dd: String, tt: String): Long {
    val t2 = tt.substring(0, 2).toLong() * 60 + tt.substring(3, 5).toLong()
    val t1 = t.substring(0, 2).toLong() * 60 + t.substring(3, 5).toLong()

    return if (m == mm) {
        val day = (dd.toLong() - d.toLong()) * 60 * 24
        day + (t2 - t1)
    } else {
        var day = 0L
        if (mm.toLong() - m.toLong() > 1) {
            for (i in (m.toLong() + 1) until mm.toLong()) {
                day += month[i.toInt()] * 60 * 24
            }
        }
        day += (dd.toLong() + (month[m.toInt()] - d.toLong())) * 60 * 24
        day + (t2 - t1)
    }
}