[백준] 28070: 유니의 편지 쓰기 - JAVA

in Algorithm on 문자열

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

풀이

누적합으로 풀 수 있는 문제이다.

(입대 월)에는 배열에 +1을 해주고 (전역 월 + 1)에는 배열에 -1을 해준다.

2000년 1월부터 9999년 12월까지 돌면서 이전 배열의 것을 더해준다.

메모리: 81920KB

시간: 824ms

언어: Java 11

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[120002];
        StringTokenizer st;
        int year;
        int month;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String[] a = st.nextToken().split("-");
            year = Integer.parseInt(a[0]);
            month = Integer.parseInt(a[1]);
            dp[year * 12 + month]++;

            String[] b = st.nextToken().split("-");
            year = Integer.parseInt(b[0]);
            month = Integer.parseInt(b[1]);
            dp[year * 12 + month + 1]--;

        }

        int max = 0;
        year = 0;
        month = 0;
        for (int i = 24000; i < 120001; i++) {
            dp[i] += dp[i - 1];
            if (dp[i] > max) {
                max = dp[i];
                year = i / 12;
                month = i % 12;
            }
        }

        if (month == 0) {
            year--;
            month = 12;
        }

        String ans;
        if (month < 10) {
            ans = year + "-0" + month;
        } else {
            ans = year + "-" + month;
        }

        System.out.println(ans);

    }

}