[leetcode] 729. My Calendar I 파이썬 코드

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

 

double booking이 아니면 캘린더에 이벤트를 집어넣을 수 있고 True를 반환하고, double booking 이면 False를 반환해야 한다. MyCalender 라는 클래스를 완성하고, book 메서드를 구현해야 한다.

double booking은 어떤 이벤트가 이미 캘린더에 있을 때 그 이벤트와 시간이 겹치면 double booking이다. 시간이 겹친다는 것을 표현하면, 후보 이벤트가 이미 캘린더 안에 있는 이벤트의 start와 end 시간 사이에 있으면 안 된다.

 

class MyCalendar(object):
    def __init__(self):
        self.dates = []

    def book(self, start, end):
        if len(self.dates) == 0:
            self.dates.append([start, end])
            return True
        for i in range(len(self.dates)):
            dstart = self.dates[i][0]
            dend = self.dates[i][1]
            if end <= dstart or dend <= start:
                continue
            else:
                return False
        self.dates.append([start, end])
        return True

 

나는 어떻게 풀었냐하면, 캘린터에 이미 들어있는 이벤트와 한 번씩 모두 비교를 해서 (for문) 후보 이벤트를 넣는 방식으로 해결했다. 

 

내가 생각한 방식

 

후보 이벤트의 end 지점이 dstart 보다 작거나 같다면, 또는 (OR) 후보 이벤트의 start 지점이 dend 보다 크거나 같다면 시간이 겹치지 않으므로 캘린더에 넣을 수 있다. 그러나 캘린더에 있는 모든 이벤트와 비교해야 하므로 continue로 하고 넘어간다. 그리고 만약에 조건을 만족하지 않으면 return False를 한다. 그런데 for 문을 다 돌았는데도 겹치는 게 없다면, 캘린더에 넣을 수 있다는 뜻이므로 캘린더에 append 하고, return True를 해준다. 

 

 

 

그러나 내 코드는 그렇게 효율적이지 않았다.

 

로직은 같지만, 좀 더 깔끔하게 코드를 다음과 같이 짤 수 있다.

class MyCalendar:
    def __init__(self):
        self.dates = []

    def book(self, start: int, end: int) -> bool:
        if len(self.dates) == 0:
            self.dates.append((start, end))
            return True
        for s, e in self.dates:
            if not(end <= s or e <= start):
                return False
        self.dates.append((start, end))
        return True

 

 

---

이것보다 더 효율적으로 만들 수는 없을까?

로직은 같지만, 다른 자료구조를 써보자. Binary Search Tree!

 

class Tree:
    def __init__(self, start, end):
        self.left = None
        self.right = None
        self.start = start
        self.end = end

    def insert(self, start, end):
        curr = self
        while True:
            if start >= curr.end:
                if not curr.right:
                    curr.right = Tree(start, end)
                    return True
                curr = curr.right
            elif end <= curr.start:
                if not curr.left:
                    curr.left = Tree(start, end)
                    return True
                curr = curr.left
            else:
                return False

class MyCalendar:
    def __init__(self):
        self.root = None

    def book(self, start: int, end: int) -> bool:
        if not self.root:
            self.root = Tree(start, end)
            return True
        return self.root.insert(start, end)

 

 

 

참고

https://youtu.be/fIxck3tlId4?si=wiSV_9ow3C0GAWj7