문제
부품 대여 기록이 주어질 때, 대여 기한(L)을 초과한 회원별 벌금을 계산하라. 벌금은 (초과 시간(분) * 분당 벌금 F)이다.
입력
첫째 줄에 기록 수 N, 대여 기한 L (DDD/HH:MM 형식), 분당 벌금 F가 주어진다. 이후 N줄에 날짜/시간, 부품명, 회원명이 주어진다. 같은 부품을 같은 회원이 다시 빌리면 반납으로 처리한다.
출력
벌금이 있는 회원을 사전순으로 이름과 벌금을 출력한다. 벌금 대상이 없으면 -1을 출력한다.
예제
| 입력 | 출력 |
|---|---|
6 3/00:00 10 2021-01-01 09:00 Arduino Badaldong 2021-01-01 09:00 Thermocouple Badaldong 2021-01-04 09:01 Arduino Badaldong 2021-01-04 09:01 Thermocouple Badaldong 2021-01-01 09:00 Arduino ChangYalkGuem 2021-01-04 09:00 Arduino ChangYalkGuem | Badaldong 20 |
풀이
HashMap으로 회원별 대여 현황을 관리하고, 반납 시 기간 초과 여부를 확인하여 벌금을 계산한다.
- 대여 기한 L을 분 단위로 변환한다 (일 * 24 * 60 + 시 * 60 + 분)
- 날짜/시간을 분 단위 정수로 변환하는 함수를 사용한다 (월별 누적일 배열 활용)
- 회원별 HashMap 안에 부품별 대여 시각을 저장한다
- 같은 회원이 같은 부품을 다시 빌리면 반납으로 처리:
(반납 시각 - 대여 시각) > L이면 초과 시간 * F를 벌금에 누적 - 벌금이 있는 회원을 PriorityQueue로 사전순 정렬하여 출력한다
핵심 아이디어: 2중 HashMap(회원 → 부품 → 대여 시각)으로 O(1) 조회/삽입/삭제가 가능하며, 같은 부품의 재등장을 반납으로 처리하는 토글 방식이다.
코드
package day349;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.HashMap;
import java.util.PriorityQueue;
public class Day331BOJ21942부품대여장 {
static int N, L, F;
static PriorityQueue<String[]> ans; // 정답 출력 정렬 큐
static HashMap<String, Long> tmp; // 벌금자 Hash Map
static HashMap<String, HashMap<String, Integer>> map; // 회원 별 대여 현황
static int[] m = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
static int[] days;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(st.nextToken());
String tmpL = st.nextToken();
String[] s = tmpL.split("/");
String[] ss = s[1].split(":");
L = Integer.parseInt(s[0]) * 24 * 60 + Integer.parseInt(ss[0]) * 60 + Integer.parseInt(ss[1]);
F = Integer.parseInt(st.nextToken());
ans = new PriorityQueue<>((o1, o2) -> o1[0].compareTo(o2[0]));
tmp = new HashMap<>();
map = new HashMap<>();
days = new int[12];
for (int i = 1; i < 12; i++)
days[i] = m[i - 1] + days[i - 1];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
String[] d = st.nextToken().split("-");
String[] t = st.nextToken().split(":");
String b = st.nextToken();
String u = st.nextToken();
int m = convert(d[1], d[2], t[0], t[1]);
if (map.containsKey(u)) { // 첫 대여 인지
if (map.get(u).containsKey(b)) { // 첫 장비 인지
int min = map.get(u).get(b);
long dif = m - min; // 아..
if (dif > L) { // 기간을 초과했는 지
Long p = (dif - L) * F; // 아..
if (tmp.containsKey(u)) { // 초범이 아닌지
tmp.put(u, tmp.get(u) + p);
} else {
tmp.put(u, p);
}
}
map.get(u).remove(b);
} else {
map.get(u).put(b, m);
}
} else {
HashMap<String, Integer> tmp = new HashMap<>();
tmp.put(b, m);
map.put(u, tmp);
}
}
tmp.forEach((u, p) -> {
ans.add(new String[] { u, " " + p });
});
if (ans.isEmpty()) {
System.out.println(-1);
} else {
while (!ans.isEmpty()) {
String[] r = ans.poll();
sb.append(r[0] + r[1]).append("\n");
}
System.out.println(sb);
}
br.close();
}
private static int convert(String month, String day, String hour, String minute) {
return days[Integer.parseInt(month) - 1] * 24 * 60 + Integer.parseInt(day) * 24 * 60
+ Integer.parseInt(hour) * 60 + Integer.parseInt(minute);
}
}복잡도
- 시간: O(N log N) (PriorityQueue 정렬)
- 공간: O(N)