a-069-design-twitter2026-07-25mediumleetcode #355neetcode150

트위터 설계

#hash-table#linked-list#design#heap-priority-queue

문제

· problem

P.a-069-design-twitter

트위터 설계

사용자가 트윗을 작성하고, 다른 사용자를 팔로우/언팔로우하며, 사용자의 뉴스 피드에서 10개의 가장 최근 트윗을 볼 수 있는 간단한 버전의 트위터를 설계하세요. Twitter 클래스를 구현하세요: - Twitter() 트위터 객체를 초기화합니다. - void postTweet(int userId, int tweetId) 사용자 userId가 ID tweetId를 가진 새 트윗을 작성합니다. 이 함수를 호출할 때마다 고유한 tweetId가 전달됩니다. - List<Integer> getNewsFeed(int userId) 사용자의 뉴스 피드에서 10개의 가장 최근 트윗 ID를 검색합니다. 뉴스 피드의 각 항목은 사용자가 팔로우한 사용자나 사용자 자신이 작성한 것이어야 합니다. 트윗은 가장 최근부터 가장 오래된 순서로 정렬되어야 합니다. - void follow(int followerId, int followeeId) ID가 followerId인 사용자가 ID가 followeeId인 사용자를 팔로우하기 시작합니다. - void unfollow(int followerId, int followeeId) ID가 followerId인 사용자가 ID가 followeeId인 사용자를 언팔로우하기 시작합니다.

제약

· 1 ≤ userId, followerId, followeeId ≤ 500
· 0 ≤ tweetId ≤ 10^4
· All tweets have unique IDs
· At most 3*10^4 calls will be made to postTweet, getNewsFeed, follow, and unfollow
· A user cannot follow themselves

// 지문은 본인 언어 요약 — 원문은 위 링크에서

입출력 예시

example 1input → output

["Twitter","postTweet","getNewsFeed","follow","postTweet","getNewsFeed","unfollow","getNewsFeed"]
[[],[1,5],[1],[1,2],[2,6],[1],[1,2],[1]]

[null, null, [5], null, null, [6, 5], null, [5]]

사전 사고

· pre-solve

● 1리스트 출력→● 2선택→● 3정답 공개

☐
사용자가 자신의 트윗을 뉴스 피드에서 볼 수 있나요?
☐
뉴스 피드에서 반환할 트윗의 최대 개수는 얼마인가요?
☐
자신을 팔로우할 수 있나요?
☐
이미 팔로우하고 있는 사용자를 다시 팔로우하면 어떻게 되나요?
☐
모든 트윗 ID가 고유한가요?
☐
오래된 트윗을 자동으로 삭제해야 하나요?
☐
데이터를 파일에 저장해야 하나요?
☐
입력값 검증이 필요한가요?

던질 질문에 체크하고 확인을 누르세요

// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)

논리 구조

· logic

● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개

// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.

step 1· 타임스탬프 카운터 초기화

○

self.count = 0

○

self.timestamp = 1

○

self.time = {}

step 2· 카운터 감소로 최신순 정렬 보장

○

self.count -= 1

○

self.count += 1

○

# No counter update

step 3· 사용자를 자신의 팔로우 목록에 추가

○

self.followMap[userId].add(userId)

○

# Don't add user to followees

○

if userId not in self.followMap[userId]: self.followMap[userId].add(userId)

step 4· 모든 팔로우 대상의 최신 트윗을 힙에 추가│ 중첩

○

heapq.heappush(minHeap, [count, tweetId, followeeId, index - 1])

○

heapq.heappush(minHeap, [tweetId, followeeId])

○

minHeap.append([count, tweetId, followeeId, index - 1])

step 5· 최소 힙에서 가장 최신 트윗 추출│ 중첩

○

count, tweetId, followeeId, index = heapq.heappop(minHeap)

○

count, tweetId, followeeId, index = minHeap[0]

○

heapq.heapreplace(minHeap, [newCount, newTweetId, followeeId, newIndex])

step 6· 같은 사용자의 다음 오래된 트윗을 힙에 추가│ │ 중첩

○

heapq.heappush(minHeap, [count, tweetId, followeeId, index - 1])

○

heapq.heappush(minHeap, [count, tweetId, followeeId, index])

○

if index > 0: heapq.heappush(minHeap, [count, tweetId, followeeId, index - 1])

각 슬롯에 한 줄씩 골라보세요

// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.

문제풀이 · 트레이스

· solve

solution.py

class Twitter:

    def __init__(self):

        self.count = 0

        self.tweetMap = defaultdict(list)  # userId -> list of [count, tweetIds]

        self.followMap = defaultdict(set)  # userId -> set of followeeId

    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]:

        res = []

        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(res) < 10:

            count, tweetId, followeeId, index = heapq.heappop(minHeap)

            res.append(tweetId)

            if index >= 0:

                count, tweetId = self.tweetMap[followeeId][index]

                heapq.heappush(minHeap, [count, tweetId, followeeId, index - 1])

        return res

    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)

머릿속 dry-run 케이스

// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.

case 1

["Twitter","postTweet","getNewsFeed","follow","postTweet","getNewsFeed","unfollow","getNewsFeed"]
[[],[1,5],[1],[1,2],[2,6],[1],[1,2],[1]]

→

[null, null, [5], null, null, [6, 5], null, [5]]

// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.