[DSA][Heap] 06. Design Twitter

LeetCode 355

 

06. Design Twitter

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and is able to see the 10 most recent tweets in the user's news feed.

Implement the Twitter class:
- Twitter() Initializes your twitter object.
- void postTweet(int userId, int tweetId) Composes a new tweet with ID tweetId by the user userId. Each call to this function will be made with a unique tweetId.
- List<Integer> getNewsFeed(int userId) Retrieves the 10 most recent tweet IDs in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user themself. Tweets must be ordered from most recent to least recent.
- void follow(int followerId, int followeeId) The user with ID followerId started following the user with ID followeeId.
- void unfollow(int followerId, int followeeId) The user with ID followerId started unfollowing the user with ID followeeId.

 

 

[질문하기]

- follow 함수가 동일한 (followerId, followeeId) 인자로 여러 번 호출될 수 있나요?

- unfollow 함수가 아직 follow하지 않은 (followerId, followeeId) 관계에 대해 호출될 수 있나요?

 

 

[풀이 1] Max Heap

class Twitter:
    def __init__(self):
        self.postMap = defaultdict(list)
        self.followMap = defaultdict(set)
        self.timestamp = 0

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.postMap[userId].append([self.timestamp, tweetId])
        self.timestamp -= 1

    def getNewsFeed(self, userId: int) -> List[int]:
        postHeap = []

        # Add user's own tweets
        for post in self.postMap[userId]: # postHeap += self.postMap[userId]로 하면 원본 공유
            heapq.heappush(postHeap, post)

        # Add followees' own tweets
        for followeeId in self.followMap[userId]:
            for post in self.postMap[followeeId]:
                heapq.heappush(postHeap, post)
        
        tweetId = []
        for i in range(10):
            if len(postHeap):
                tweetId.append(heapq.heappop(postHeap)[1])
            else:
                break
        return tweetId

    def follow(self, followerId: int, followeeId: int) -> None:
        self.followMap[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        if followeeId in self.followMap[followerId]:
            self.followMap[followerId].remove(followeeId)

각 함수에서 구현해야 할 기능의 형태(자료구조)를 먼저 생각해 보면, follow / unfollow는 어떤 user가 어떤 user를 follow 했고, unfollow 했는지, 즉 특정 userId 기준으로 최종적으로 follow 하고 있는 userId들의 집합(set)을 알 수 있어야 한다.

postTweet에서는 어떤 user가 어떤 tweet을 남겼는지를 저장해야 하는데, getNewsFeed와 같이 생각해보면 자기 자신이 올린 tweet뿐만 아니라 follow 하고 있는 user들의 tweet도 확인할 수 있어야 한다. 이때 user가 follow 하고 있는 userId는 follow / unfollow를 통해 알 수 있고, 해당 userId들이 올린 tweet은 postTweet에 저장된 내용을 통해 알 수 있으므로, 이것을 recent 순서대로 10개까지 가져올 수 있어야 한다. recent 순서를 알기 위해서 post할 때 timestamp를 같이 저장해 두면 되고, 여러 user들의 tweet을 모아서 최신 순으로 가져오는 과정에서는 heap을 사용하면 좋다는 걸 알 수 있다. (10개까지만 저장하는 방식을 사용하면 공간 복잡도를 줄일 수 있다.)

추가로 시간 순서상 recent = timestamp가 큰 값이므로 원래대로 라면 max heap을 써야 하지만, timestamp를 1씩 감소시키면서 저장하면, min heap으로 recent 순서대로 정렬이 가능하다.

 

몇 가지 주의 포인트는

• getNewsFeed에서 여러 user의 tweet을 하나의 리스트로 합칠 때, post += self.postMap[userId]처럼 하면 원본 리스트가 공유돼서 훼손될 수 있다. 따라서 for문 돌면서 개별적으로 추가해주어야 한다.
• follow에 중복된 인자가 들어올 수 있으므로 list 대신 set을 쓰는 게 좋고, unfollow에서 follow하지 않은 userId가 들어올 수 있어서, 그냥 remove() 하면 에러가 날 수 있다.

 

⏱️ 시간복잡도

모든 user의 수를 N, user 당 평균 tweet 수를 m, user 당 평균 follow 수를 M라 하면,

postTweet() : tweet을 list에 append 하는 연산만 있으므로 O(1)follow() / unfollow() : hashMap에서 원소를 찾고 set에 원소를 추가하거나 제거하는 연산만 있으므로 O(1)getNewsFeed() : 특정 userId가 follow하고 있는 모든 followeeId들의 post를 heap 연산하므로 O(M * m * log(M * m))

🧠 공간복잡도

모든 user의 수를 N, user 당 평균 tweet 수를 m, user 당 평균 follow 수를 M라 하면,

postTweet() : 각 user가 저장한 tweet을 모두 저장하므로 O(N * m)

follow() / unfollow() : 각 user가 follow한 ID를 모두 저장하므로 O(N * M)

getNewsFeed() : 각 user가 follow한 ID에 대한 post를 모두 저장하므로 O(M * m)

따라서 공간 복잡도는 O(N*m + N*M + M*m)이다.