문제

문제링크

접근

• 처음에는 dp, 그 다음에는 슬라이딩 윈도우로 풀어보려고 했지만 공간적, 시간적 복잡도가 문제 출제자께 죄송할 정도로 터무니 없을 것 같아 아니라고 판단하였다.
• 그리고 한참 고민하다가, 임계값을 이용하라는 힌트를 가지고 아래와 같이 풀이하였다.
• 정답을 확인하고 다른 사람들의 풀이를 보는데, LocalDateTime으로 바로 연산한 사람을 못 봤다..!

소스 코드

import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;

class Main {
    static int N, M;
    static int[] Group;

    public static void main(String[] args) throws Exception {
        String lines[] = {"2016-09-15 01:00:04.002 2.0s",
"2016-09-15 01:00:07.000 2s"};

        Solution sol = new Solution();
        System.out.println("result : " + sol.solution(lines));
    }
}

class Solution {
    public int solution(String[] lines) throws Exception {
        int answer = 0;
        int lineCnt = lines.length;

        LocalDateTime startTimes[] = new LocalDateTime[lineCnt];
        LocalDateTime endTimes[] = new LocalDateTime[lineCnt];
        DateTimeFormatter formatter = DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss.SSS");

        for (int i = 0; i < lineCnt; i++) {
            LocalDateTime end = LocalDateTime.parse(lines[i].substring(0, 23), formatter);
            Double lastTaskTime = Double.parseDouble(lines[i].substring(24, lines[i].length() - 1));
            LocalDateTime start = end.plusNanos((long) (lastTaskTime * 1000000000) + 1);

            endTimes[lineCnt - i - 1] = end;
            startTimes[lineCnt - i - 1] = start;
        }

        for (int i = 0; i < lineCnt; i++) {
            int cnt = 1;
            if (answer >= lineCnt - i)
                break;
            for (int j = i + 1; j < lineCnt; j++) {
                if (startTimes[j].isAfter(endTimes[j].plusSeconds(1)))
                    cnt++;
            }
            answer = answer > cnt ? answer : cnt;
        }
        return answer;
    }
}