10/20 (금) 트위터 클래스 디자인하기 TIL

공부한 것

LeetCode #355. Design Twitter
Design Twitter - LeetCode
Can you solve this real interview question? 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. Example 1: Input ["Twitter", "postTweet", "getNewsFeed", "follow", "postTweet", "getNewsFeed", "unfollow", "getNewsFeed"] [[], [1, 5], [1], [1, 2], [2, 6], [1], [1, 2], [1]] Output [null, null, [5], null, null, [6, 5], null, [5]] Explanation Twitter twitter = new Twitter(); twitter.postTweet(1, 5); // User 1 posts a new tweet (id = 5). twitter.getNewsFeed(1); // User 1's news feed should return a list with 1 tweet id -> [5]. return [5] twitter.follow(1, 2); // User 1 follows user 2. twitter.postTweet(2, 6); // User 2 posts a new tweet (id = 6). twitter.getNewsFeed(1); // User 1's news feed should return a list with 2 tweet ids -> [6, 5]. Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5. twitter.unfollow(1, 2); // User 1 unfollows user 2. twitter.getNewsFeed(1); // User 1's news feed should return a list with 1 tweet id -> [5], since user 1 is no longer following user 2. Constraints: * 1 <= userId, followerId, followeeId <= 500 * 0 <= tweetId <= 104 * All the tweets have unique IDs. * At most 3 * 104 calls will be made to postTweet, getNewsFeed, follow, and unfollow.
https://leetcode.com/problems/design-twitter/description/
⇒ 간소화된 트위터 클래스를 구현하는 문제였다. 구현해야 하는 메소드로는 postTweet, follow, unfollow, getNewsFeed 가 있음.
- 풀이 코드:
  필요한 자료구조는 다음과 같다:
  1. 누가 누구를 팔로우하고 있는지 {followerId: {followee1:true,followee2:true, ...}}
  1. 트윗이 등록된 순서대로 저장하고 있는 것 하나. 0번이 가장 오래된 트윗이다. [tweet1, tweet2, ...]
  1. 몇 번 트윗이 어떤 유저에 의해 포스팅됐는지. {postId: userId}
  메소드 설계: 위의 자료구조는 각 메소드에서 대략 다음과 같이 이용된다.
  1. postTweet: (자료구조)2와 3에 넣는다. {postId: userId}
  1. follow: (자료구조)1에 넣는다 {followerId: followeeId}
  1. unfollow: (자료구조)1에서 뺀다 delete{followerId: followeeId}
  1. getNewsFeed: (자료구조)2에서 최신 포스팅부터 훑으며, 3에서 각 포스트 id 작성자를 찾고 1에서 조회하여 본인 포함 팔로우 중인 id에 속하면 선택한다. 10개가 선택되면 2를 훑는 것을 멈춘다.
```
class Twitter1 {
    private whoFollowsWhom: { [key: number]: { [key: number]: boolean } } // {follwoerid: followeeId}
    private tweetOrder: number[];        // [post1, post2, ...]
    private tweetPostedBy: { [key: number]: number }  // {postId: userId}
    constructor() {
        this.whoFollowsWhom = {};
        this.tweetOrder = [];
        this.tweetPostedBy = {};
    }

    postTweet(userId: number, tweetId: number): void {
        this.tweetOrder.push(tweetId);
        this.tweetPostedBy[tweetId] = userId;
        //? FIXME: 하나의 tweet ID를 여러 유저가 등록하는 경우? 
    }
    
    follow(followerId: number, followeeId: number): void {
        if (this.whoFollowsWhom[followerId] === undefined)
            this.whoFollowsWhom[followerId] = {};
        this.whoFollowsWhom[followerId][followeeId] = true;
    }
    
    unfollow(followerId: number, followeeId: number): void {
        delete this.whoFollowsWhom[followerId]?.[followeeId];
    }

    getNewsFeed(userId: number): number[] {
        // => getNewsFeed: 2에서 최신 포스팅부터 훑으며, 3에서 각 포스트 id 작성자를 찾고 1에서 조회하여 본인 포함 팔로우 중인 id에 속하면 선택한다. 10개가 선택되면 2를 훑는 것을 멈춘다. 
        const newsFeed10: number[] = [];
        const followingUsers = this.whoFollowsWhom[userId] ?? {};
        let i = this.tweetOrder.length - 1;
        
        while (newsFeed10.length < 10) {
            //? FIXME: what if total posts are less than 10? 
            if (i < 0) return newsFeed10;

            let tweetId = this.tweetOrder[i];
            let posterId = this.tweetPostedBy[tweetId];
            // 트윗 발행자가 '나'거나 '내가 팔로잉하는 사람들' 중 하나라면 newsFeed10에 추가
            if (posterId === userId || followingUsers[posterId]) {
                newsFeed10.push(tweetId);
            }
            i--;
        }

        return newsFeed10;
    }
}
```

follow 메소드에서는 다음과 같이 반드시 followerId에 대응되는 객체가 존재하도록 만들어주고 그 속성값 [followeeId]를 넣어주기 때문에 문제가 생기지 않는다:
```
follow(followerId: number, followeeId: number): void {
    //? FIXME: 자기 자신을 팔로우하는 경우?
    if (this.whoFollowsWhom[followerId] === undefined)
        this.whoFollowsWhom[followerId] = {};
    this.whoFollowsWhom[followerId][followeeId] = true;
}
```
그런데 unfollow에서는 그러한 사전 점검 없이 delete this.whoFollowsWhom[followerId]?.[followeeId];을 곧바로 실행하기 때문에, 옵셔널 체이닝을 해줘야 했다.
알게된 점: 타입스크립트에서 옵셔널 체이닝은 주의가 필요하다. this.whoFollowsWhom[followerId]?.followeeId가 아닌 this.whoFollowsWhom[followerId]?.[followeeId] 처럼 써줘야 에러가 나지 않는다.

Uploaded by N2T

공부한 것

티스토리툴바