LeetCode: 732번 (My Calendar III) [JAVA]

문제 링크

https://leetcode.com/problems/my-calendar-iii/

My Calendar III - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 누적합을 활용하여 book() 함수를 구현하기 위해 TreeMap을 활용
2. 주어진 start와 end값을 key로 가진 value에 각각 +1과 -1을 적용
3. 이후 전체 TreeMap을 돌며 누적합을 계산하는데, 이 중 최대값을 반환하면 된다.

 문제에서 요구했던 핵심 부분은 바로 book 함수인데, 주어진 start와 end를 전체 예약 일정에 반영하고 나서 전체 일정 중 가장 일정이 많이 모이게 되는 횟수를 반환하는 함수이다. 이 때 누적합을 활용하기 위해 배열을 사용해도 되지만, 이 경우 start와 end로 주어질 수 있는 최대값이 10^9이기 때문에 복잡도 측면에서 좋지 않다. 그렇기 때문에 정렬되어 있으면서 주어진 start와 end 값들 만을 활용할 수 있어야 하기에 TreeMap을 사용하면 좋다. 주어진 start와 end를 key로 가진 value 부분에 각각 +1과 -1을 적용한다. 그 다음 전체 TreeMap을 돌면서 누적합을 계산하는데, 이 중 최대값을 book 함수의 반환값으로 반환하면 된다.

 

class MyCalendarThree {
    TreeMap<Integer, Integer> treeMap;

    public MyCalendarThree() {
        treeMap = new TreeMap<>();
    }

    public int book(int start, int end) {//누적합 활용
        if (treeMap.containsKey(start)) {//start 쪽에 +1 체크
            treeMap.put(start, treeMap.get(start) + 1);
        } else {
            treeMap.put(start, 1);
        }

        if (treeMap.containsKey(end)) {//end 쪽에 -1 체크
            treeMap.put(end, treeMap.get(end) - 1);
        } else {
            treeMap.put(end, -1);
        }

        int temp = 0, result = 0;
        for (Integer value : treeMap.values()) {//전체를 돌며 누적합 중 가장 큰 값을 반환
            temp += value;

            result = Math.max(result, temp);
        }

        return result;
    }
}

결과