[BOJ21942] 부품 대여장 (자료구조, 해시맵)

 

---

 

문제 링크 

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

 

---

문제 풀이

직접 풀이 못함, 월별 일수 계산하는 방법 알게 되어 기록

 

- 문자열로 된 날짜 데이터 변환이 어려운 문제였다.

- 구현 로직은 Map 자료구조를 사용하여 상대적으로 간단했다

- 시간복잡도: O(N)  (Map 자료구조를 사용해서 O(1)에 추가/삭제 가능)

 

 

[핵심 로직]

- Map에 닉네임과 부품(key) 정보가 없는 경우 대여 이므로 HashMap 에 데이터 추가 한다

- Map에 닉네임과 부품(key) 정보가 있는 경우 반납 이므로 HashMap 제거 후 패널티 계산 수행한다

- 벌금의 경우에도 Map 자료구조 사용하여 {key: 닉네임, value: 벌금} 형태로 기록한다

 

 

실수 1. 최대치 long

- 문제에서 yyyy는 2021년으로 통일된다

- DDD/hh:mm 에서 DDD는 최대 200일 나타낸다

 

예로

1일 대여가능, 분당 4,000원의 벌금

대여일 : 2021-01-01 / 반납일 : 2021-12-31

그리고 부품 대여/반납을 혼자서 40,000번씩 했을 때

 

러프하게 계산하더라도 int 범위를 초과하게 된다

(364 * 24 * 60 (분 변환) + (hour * 60) + minute)* 4,000원(요금)

 

 

실수 2. LocalDateTime, DateTimeFormatter

2021-01-01 00:00 기준으로 초(또는 분)으로 환산 후 계산했는데, 예외 케이스도 결과값은 구해졌지만 정답 처리는 받지 못했다

private static final DateTimeFormatter FORMATTER = DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm");
private static final LocalDateTime STANDARD_DATE = LocalDateTime.parse("2021-01-01 00:00", FORMATTER);

private static long convert(String date) {
    return ChronoUnit.SECONDS.between(STANDARD_DATE, LocalDateTime.parse(date, FORMATTER));
}

 

 

실수3. 월별 날짜 계산 

- yyyy-mm-dd hh:mm 포맷을 분으로 직접 환산하는 방법으로 변경하였다

- Chat-GPT 통해 처음 알게 된 사실로 월별 일 수를 간단하게 구하는 방법이 있었다

 

① 31일로 끝나는 달: 1, 3, 5, 7, 8, 10, 12

② 30일로 끝나는 달 : 4, 6, 9, 11

③ 2월의 경우: 윤년이 아닌 경우 28일, 윤년인 경우 29일

 

윤년의 경우 보통 4년마다 발생한다
예외적으로 100의 배수해는 윤년이 아니지만, 400의 배수인 경우 윤년에 해당한다 

ex. 2000년은 윤년, 2월 29일까지 
ex. 2001년은 윤년 아님, 2월 28일까지

 

DAYS (클래스 맴버 필드) 선언시 11월의 일수를 잘못 선언해서 틀렸고, 이걸 찾는데 1시간 가까이 날려버렸다..

private static final int[] DAYS = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; 

private static long convert(String date, String time) {
    String[] dates = date.split("-");
    int month = Integer.parseInt(dates[1]);
    int day = Integer.parseInt(dates[2]);
    for (int i = 0; i < month; i++) {
        day += DAYS[i];
    }

    String[] times = time.split(":");
    int hour = Integer.parseInt(times[0]);
    int minute = Integer.parseInt(times[1]);

    // 당일인 경우 -1 해줘야 함
    return ((long) (day - 1) * 24 * 60 + (hour * 60) + minute) ;
}

 

---

제출 코드

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

public class Main {
    private static StringBuilder sb = new StringBuilder();
    private static InputProcessor inputProcessor = new InputProcessor();

    private static final int[] DAYS = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; 
    
    private static int N, F, MINUTE;
    private static String L;
    
    public static void main(String[] args) throws IOException {
        input();
        pro();
        output();
    }

    private static void input() {
        N = inputProcessor.nextInt(); // 대여장에 작성된 정보의 개수
        L = inputProcessor.next(); // 대여기간 DDD/hh:mm
        F = inputProcessor.nextInt(); // 벌금 (원/분당)

        String[] tokens = L.split("/");
        int days = Integer.parseInt(tokens[0]);

        String[] times = tokens[1].split(":");
        int hour = Integer.parseInt(times[0]);
        int minute = Integer.parseInt(times[1]);

        MINUTE += days * 24 * 60;
        MINUTE += hour * 60;
        MINUTE += minute;
    }

    private static void pro() {
        Map<String, Long> resultMap = new HashMap<>(); // 최대치
        Map<String, Map<String, Long>> bookInfoMap = new HashMap<>();
        for (int i = 1; i <= N; i++) {
            String line = inputProcessor.nextLine();
            String[] tokens = line.split(" ");
            String date = tokens[0];
            String time = tokens[1];
            String parts = tokens[2];
            String nickname = tokens[3];

            long times = convert(date, time); // 대여 시간 or 반납 시간
            if (!bookInfoMap.containsKey(nickname)) {
                bookInfoMap.put(nickname, new HashMap<>());
                bookInfoMap.get(nickname).put(parts, times);
            } else {
                Map<String, Long> bookMap = bookInfoMap.get(nickname);
                if (bookMap.containsKey(parts)) {
                    long borrowTime = bookMap.remove(parts); // 부품 반납이므로 제거
                    long diff = times - borrowTime - MINUTE; 
                    
                    if (diff > 0) {
                        long fee = diff * F;
                        resultMap.put(nickname, resultMap.getOrDefault(nickname, 0L) + fee);
                    }
                } else { //부품 대여
                    bookMap.put(parts, times);
                }
            }
        }

        if (resultMap.isEmpty()) {
            sb.append(-1);
        } else {
            List<String> keySet = new ArrayList<>(resultMap.keySet());
            Collections.sort(keySet);

            keySet.forEach(nickname -> sb.append(nickname).append(" ").append(resultMap.get(nickname)).append("\n"));
        }
    }

    private static long convert(String date, String time) {
        String[] dates = date.split("-");
        int month = Integer.parseInt(dates[1]);
        int day = Integer.parseInt(dates[2]);
        for (int i = 0; i < month; i++) {
            day += DAYS[i];
        }

        String[] times = time.split(":");
        int hour = Integer.parseInt(times[0]);
        int minute = Integer.parseInt(times[1]);

        // 당일인 경우 -1
        return ((long) (day - 1) * 24 * 60 + (hour * 60) + minute) ;
    }

    private static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static class InputProcessor {
        BufferedReader br;
        StringTokenizer st;

        public InputProcessor() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return st.nextToken();
        }

        public String nextLine() {
            String input = "";
            try {
                input = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }

            return input;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

    }
}