[ 알고리즘 ] LeetCode 1917. Leetcodify Friends Recommendations

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

본 글은 [ LeetCode ] 1917. Leetcodify Friends Recommendations을 풀고 작성한 글입니다.

문제

테이블

Table: Listens

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| user_id     | int     |
| song_id     | int     |
| day         | date    |
+-------------+---------+
There is no primary key for this table. It may contain duplicates.
Each row of this table indicates that the user user_id listened to the song song_id on the day day.

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.
Note that user1_id < user2_id.

요구사항

Write an SQL query to recommend friends to Leetcodify users. We recommend user x to user y if:

• Users x and y are not friends, and
• Users x and y listened to the same three or more different songs on the same day.

Note that friend recommendations are unidirectional, meaning if user x and user y should be recommended to each other, the result table should have both user x recommended to user y and user y recommended to user x . Also, note that the result table should not contain duplicates (i.e., user y should not be recommended to user x multiple times.).

Return the result table in any order.

The query result format is in the following example.

풀이

접근법

WHERE 구에 NOT IN 또는 NOT EXISTS 를 사용하는 경우 인덱스된 필드인 것과 관련 없이 무조건적으로 모든 값을 비교하기 때문에 비효율적이다. 따라서 LEFT JOIN 및 WHERE field IS NULL 과 같은 조건을 통해 차집합을 구하는 방법을 사용하는 게 좋다.

나의 풀이

접근법을 토대로 LEFT JOIN 구를 활용한 풀이는 아래와 같다.

WITH Users (user_id, friend_id) AS (
    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
), Recommendations (user_id, recommended_id) AS (
    SELECT
        DISTINCT Listens.user_id AS user_id,
        SubListens.user_id AS recommended_id
    FROM Listens
    JOIN Listens AS SubListens
    ON (
        Listens.user_id <> SubListens.user_id
        AND
        Listens.song_id = SubListens.song_id
        ANd
        Listens.day = SubListens.day
    )
    LEFT JOIN Users
    ON (
        Listens.user_id = Users.user_id
        AND
        SubListens.user_id = Users.friend_id
    )
    WHERE Users.user_id IS NULL
    GROUP BY Listens.user_id, SubListens.user_id, Listens.day
    HAVING COUNT(DISTINCT Listens.song_id) >= 3
)

SELECT user_id, recommended_id
FROM Recommendations

기타

LEFT JOIN 구를 사용할 때 어떻게 해야 조건에 부합하는 필드를 구할 수 있을 지 고민이 많았는데 직접 테이블을 간략하게 그려서 연결해보는 게 도움이 됐다. 앞으로 JOIN 구를 사용해야 하는 복잡한 문제를 풀 때도 그 방향성에 대한 부분 때문에 고민이 될 때 직접 몇 가지 행을 가지고 그려보는 게 도움이 될 것 같다.