[백준] 21942 부품 대여장 java

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

682

178

121

22.787%

문제

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

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

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

또한 대여기간을 정하고 대여기간을 넘길 경우 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$N$, 대여기간 L$L$, 벌금 F$F$이 공백으로 구분되어 주어진다.

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

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

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

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

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

출력

벌금을 내야하는 사람들을 사전순으로 동아리 회원 닉네임 M$M$와 내야하는 벌금을 한 줄씩 출력한다.

만약 벌금을 내야하는 사람들이 없는 경우는 -1을 출력한다.

제한

풀이

 

Map, TreeMap, Set 등을 이용한 자료구조 문제였다. 주어진 입력을 어떤 자료구조를 사용해 풀이할지 좋은 문제였다고 생각한다.

 

처음엔 Calendar 클래스를 사용해서 문제를 풀었더니 시간초과가 나서 직접 문자열을 파싱해서 계산했더니 맞게 나왔다. 그리고 벌금을 구하는 과정에서 정수 자료형을 사용하면 오버플로우가 날 수 있으니 long 자료형을 써주도록 하면 된다.

 

import java.io.*;
import java.util.*;

class RentInfo {
    Map<String, String> bookList;
    RentInfo(String date, String parts) {
        bookList = new HashMap<>();
        this.bookList.put(parts, date);
    }
}

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static StringBuilder sb;
    static int N, F;
    static String bookInfo;
    static Map<String, RentInfo> rentList;
    static Map<String, Long> penaltyList;
    static int[] month = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

    public static void main(String[] args) throws IOException {
        init();
        solve();
        if(penaltyList.isEmpty()) System.out.println(-1);
        else {
            penaltyList.forEach((key, value) -> {
                sb.append(key+" "+value+"\n");
            });
            System.out.print(sb);
        }
    }

    static void init() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        bookInfo = st.nextToken();
        F = Integer.parseInt(st.nextToken());
        rentList = new HashMap<>();
        penaltyList = new TreeMap<>();
    }

    static void solve() throws IOException {
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String date = st.nextToken();
            date = date + " " + st.nextToken();
            String partsName = st.nextToken();
            String borrower = st.nextToken();

            //빌린 목록에 해당 사람이 있는지 판별
            if(!rentList.containsKey(borrower)) {
                // 없다면 대여한다는 뜻이니 생성 후 빌린 목록에 부품 이름 저장
                rentList.put(borrower, new RentInfo(date, partsName));
            } else {
                //있다면 빌린 목록에 같은 이름이 있는지 판별
                if(rentList.get(borrower).bookList.containsKey(partsName)) {
                    //같은 이름이 있다면 반납이니 정보를 꺼낸다.
                    String start = rentList.get(borrower).bookList.get(partsName);
                    //꺼낸 정보로 벌금을 부과해야 하는지 판단한다.
                    long penalty = getPenalty(start, date);
                    //부과해야 한다면 리스트에 값을 갱신하고 반납처리를 한다.
                    if(penalty != -1) {
                        penaltyList.put(borrower, penaltyList.getOrDefault(borrower, (long)0)+penalty);
                        rentList.get(borrower).bookList.remove(partsName);
                    } else {
                        //부과하지 않아도 된다면 반납 처리를 한다.
                        rentList.get(borrower).bookList.remove(partsName);
                    }
                } else {
                    //같은 이름이 없다면 대여한다는 뜻이니 대여 정보 저장
                    rentList.get(borrower).bookList.put(partsName, date);
                }
            }
        }
    }

    static long getPenalty(String start, String end) {
        /*
        yyyy-MM-dd HH:mm
        ddd/HH:mm
         */
        int[] startInfo = new int[4];
        int[] endInfo = new int[4];

        for(int i = 0; i < 4; i++) {
            if(i == 0) {
                startInfo[i] = Integer.parseInt(start.substring(5, 7));
                endInfo[i] = Integer.parseInt(end.substring(5, 7));
            }
            if(i == 1) {
                startInfo[i] = Integer.parseInt(start.substring(8, 10));
                endInfo[i] = Integer.parseInt(end.substring(8, 10));
            }
            if(i == 2) {
                startInfo[i] = Integer.parseInt(start.substring(11, 13));
                endInfo[i] = Integer.parseInt(end.substring(11, 13));
            }
            if(i == 3) {
                startInfo[i] = Integer.parseInt(start.substring(14, 16));
                endInfo[i] = Integer.parseInt(end.substring(14, 16));
            }
        }
        long bookDay = Integer.parseInt(bookInfo.substring(0, 3));
        long bookHour = Integer.parseInt(bookInfo.substring(4, 6));
        long bookMinute = Integer.parseInt(bookInfo.substring(7, 9));

        long sumMinute1 = (getSumOfArr(1, startInfo[0])+startInfo[1]) * 1440 + startInfo[2] * 60 + startInfo[3];
        long sumMinute2 = (getSumOfArr(1, endInfo[0])+endInfo[1]) * 1440 + endInfo[2] * 60 + endInfo[3];
        long sumMinute3 = bookDay * 1440 + bookHour * 60 + bookMinute;

        if(sumMinute1 + sumMinute3 < sumMinute2) {
            return (sumMinute2 - (sumMinute1 + sumMinute3)) * F;
        }

        return -1;
    }

    static long getSumOfArr(int s, int e) {
        long sum = 0;
        for(int i = s; i < e; i++) {
            sum += month[i];
        }
        return sum;
    }
}