[코테연습] 729. My Calendar I

- 이진트리 / 배열 문제

 

https://leetcode.com/problems/my-calendar-i/description/?envType=daily-question&envId=2024-09-26

 

- 문제분석

1. int[] arr = { start, end } 형태의 배열이 있다.

2. 해당 배열을 MyCalender 라는 클래스 함수에 넣었을때, 기간이 겹치지 않으면 true 를 반환한 뒤 해당 일정을 더한다.

3. 기간이 겹치면 false 를 반환한다.

4. start ~ end 의 기간 동안의 이벤트는 다른 일자와 겹치지 못한다.

 

- 문제풀이

1. TreeMap 을 선언한다.

2. TreeMap 을 { end( key ) = start (value) } 구조로 구성될 것이므로, Integer.MAX_VALUE 로 초기화한다. ( 최대값 )

3. book 함수를 만들때, TreeMap의 higherEntry( start ) 함수로 start 의 숫자 보다 작은 값중 가장 큰 값을 구한다.

4. 이때 반환되는 값은 Map.Entry 클래스의 end (key) 와 start ( value ) 형태이다.

4-1. 즉 start 보다 작은 end 값을 비교하여 가장 가까이 있는 숫자를 구한 값.

5. Map.Entry 클래스의 getValue ( start ) 값이 book 의 매개변수 end보다 작은지 확인한다.

5-1. 즉 book의 매개변수 start 는 TreeMap 에서 가장 가까이 있는 end 보다 커야한다. ( start > TreeMap (end) )

5-2 book 의 매개변수 end 는 TreeMap 에서 가장 가까이 있는 start 보다 작거나 같아야한다.

 

class MyCalendar {
    TreeMap<Integer, Integer> map = new TreeMap<>();
    public MyCalendar() {
        // TreeMap 을 사용하면 값을 비교할때 유용하다. 
        // cellingEntry, higherEntry, floorKey, lowerKey 함수로 현재 값에서 가장 근사치의 최소값 최대값 비교 가능.
        map.put(Integer.MAX_VALUE, Integer.MAX_VALUE);
    }
    
    public boolean book(int start, int end) {
        //{end (key) : start (value)};
        Map.Entry<Integer, Integer> pair = map.higherEntry(start); //map 에서 start 에 해당하는 key 값 보다 큰 숫자 중 가장 큰 숫자 Map 엔트리 반환
        boolean res = end <= pair.getValue(); // end 값과 map 에서 key보다 큰 숫자중 가장 큰 숫자와 비교한다.
        if (res) {
            map.put(end, start);
        }
        return res;
    }
}