[1스4코2파] # 239. LeetCode 355. Design Twitter

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (239차)
[4코1파] 2023.01.13~ (231일차)
[1스4코1파] 2023.04.12~ (142일차)
[1스4코2파] 2023.05.03 ~ (120일차)

Today :

2023.08.30 [239일차]
LeetCode 355. Design Twitter
https://leetcode.com/problems/design-twitter/

355. Design Twitter

문제 설명

Twitter class를 구현하는 문제로,
postTweet, getNewsFeed, follow, unfollow 총 4개의 메소드를 가지고 있고 각 메소드들의 기능은
(1) postTweet의 경우
유저 userId의 tweetId ID로 새 트윗을 작성하는데, 각 함수에 대한 호출은 이 고유한 tweetId를 사용하여 이루어진다.
(2) getNewsFeed의 경우
userId를 인자로 받아서 해당 id를 가진 유저가 뉴스피드에서 가장 최근 트윗 ID 10개를 검색해준다. 뉴스피드의 각 항목은 사용자가 팔로우한 사용자로부터 나오는 트위터이고, 가장 최근의 것부터 가장 최근의 것 순으로 정렬되어야 한다.
(3) follow의 기능은 followerId와 followeeId를 받아서 ID가 followerId인 사용자가 ID가 followeeId인 사용자를 팔로우하기 시작하는 기능
(4) unfllow의 기능은 followerId와 followeeId를 받아서 ID가 followerId인 사용자가 ID가 followeeId인 사용자를 팔로우를 끊는(언팔하는) 기능 이다.

문제 풀이 방법

getNewsFeed 메소드에서 최근 10개를 오름차순으로 가져오기 위해서 minHeap을 사용하고, 최신을 뽑아오기 위해 count 인자를 넣어서 -1을 해가면서, 가장 최신의 feed를 return 해온다.

엣지 케이스로 NewsFeed가 10개가 넘었을 때 10개 까지만 return 해오는 것과 한 유저가 여러개의 tweetid를 가지고 있을 때를 잘 구현해야 함.

minheap에 최신의 게시물인지 알 수 있는 변수 count와 고유 userid, 그리고 해당 id가 사용하는 tweetid 와 인덱싱 변수를 넣어줘야 한다.

내 코드

class Twitter:

    def __init__(self):
        self.count = 0
        self.tweetMap = defaultdict(list)
        self.followMap = defaultdict(set)

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.tweetMap[userId].append([self.count, tweetId])
        self.count-=1
        
    def getNewsFeed(self, userId: int) -> List[int]:
        ans = []
        minHeap = []
        self.followMap[userId].add(userId)

        for followeeId in self.followMap[userId]:
            if followeeId in self.tweetMap:
                index = len(self.tweetMap[followeeId])-1
                count, tweetId = self.tweetMap[followeeId][index]
                heapq.heappush(minHeap, [count, tweetId, followeeId, index-1])

        while minHeap and len(ans)<10:
            count, tweetId, followeeId, index = heapq.heappop(minHeap)
            ans.append(tweetId)
            if index>=0:
                count, tweetId = self.tweetMap[followeeId][index]
                heap.heappush(minHeap, [count, tweetId, followeeId, index-1])
        return ans

    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)

증빙

여담

이거 풀고 이해하는데 2일걸림