[ 알고리즘 ] LeetCode 1892. Page Recommendations II

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ LeetCode ] 1892. Page Recommendations II를 풀고 작성한 글입니다.

문제

테이블

Table: Friendship

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| user1_id      | int     |
| user2_id      | int     |
+---------------+---------+
(user1_id, user2_id) is the primary key for this table.
Each row of this table indicates that the users user1_id and user2_id are friends.

Table: Likes

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| user_id     | int     |
| page_id     | int     |
+-------------+---------+
(user_id, page_id) is the primary key for this table.
Each row of this table indicates that user_id likes page_id.

요구사항

You are implementing a page recommendation system for a social media website. Your system will recommended a page to user_id if the page is liked by at least one friend of user_id and is not liked by user_id .

Write an SQL query to find all the possible page recommendations for every user. Each recommendation should appear as a row in the result table with these columns:

• user_id : The ID of the user that your system is making the recommendation to.
• page_id : The ID of the page that will be recommended to user_id .
• friends_likes : The number of the friends of user_id that like page_id.

Return result table in any order.

The query result format is in the following example.

풀이

접근법

LEFT JOIN 구 및 WHERE field IS NULL 구를 활용해 WHERE field NOT IN 구보다 훨씬 빠르게 차집합을 구할 수 있다. NOT IN 구의 경우 인덱스된 테이블인 것과 무관하게 무조건적으로 모든 값을 비교하는 것에 반해 LEFT JOIN 구 및 WHERE IS NULL 구는 인덱스 테이블을 사용하게 되기 때문이다.

이를 활용하여 친구가 좋아한 페이지에 대해서는 JOIN 구를, 본인이 좋아한 페이지에 대해서는 LEFT JOIN 구를 사용하여 친구와 본인 모두 동일하게 좋아하는 경우를 조건으로 하여 결합하면 NULL 값을 가지는 경우가 곧 본인은 좋아한 적 없는데 친구만 좋아하는 페이지이기에 추천 받을 페이지가 된다.

나의 풀이

접근법을 토대로 푼 쿼리 결과는 아래와 같다.

user1_id 및 user2_id 필드를 뒤집은 테이블을 UNION ALL 키워드를 사용해 수직 결합을 한 다음 이에 대해 좌측 필드가 곧 user_id 로 두고 우측 필드 기준으로 추천 받고자 하는 page_id 필드를 Likes 테이블을 JOIN 구를 통해 수평 결합하여 구해낸다. 이후 LEFT JOIN 구를 활용하여 user_id 필드와 Likes 필드의 user_id 필드가 동일하면서 동시에 이전에 JOIN 구로 수평 결합한 필드 중 page_id 필드의 값이 LEFT JOIN 구와 동일한 경우를 조건으로 한다. 이렇게 접근하면 NULL 값을 반환하는 게 곧 본인이 좋아하지 않았는데 본인과 친구를 맺고 있는 사용자가 좋아한 page_id 필드가 된다.

SELECT
    Users.user_id,
    FriendsLikes.page_id,
    COUNT(FriendsLikes.user_id) AS friends_likes
FROM (
    SELECT
        user1_id AS user_id,
        user2_id AS friend_id
    FROM Friendship
    UNION ALL
    SELECT
        user2_id AS user_id,
        user1_id AS friend_id
    FROM Friendship
) AS Users
JOIN Likes AS FriendsLikes
ON Users.friend_id = FriendsLikes.user_id
LEFT JOIN Likes AS MyLikes
ON (
    Users.user_id = MyLikes.user_id
    AND
    FriendsLikes.page_id = MyLikes.page_id
)
WHERE MyLikes.user_id IS NULL
GROUP BY Users.user_id, FriendsLikes.page_id;