[ 알고리즘 ] LeetCode 1635. Hopper Company Queries I

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

본 글은 [ LeetCode ] 1635. Hopper Company Queries I을 풀고 작성한 글입니다.

문제

테이블

Table: Drivers

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| driver_id   | int     |
| join_date   | date    |
+-------------+---------+
driver_id is the primary key for this table.
Each row of this table contains the driver's ID and the date they joined the Hopper company.

Table: Rides

+--------------+---------+
| Column Name  | Type    |
+--------------+---------+
| ride_id      | int     |
| user_id      | int     |
| requested_at | date    |
+--------------+---------+
ride_id is the primary key for this table.
Each row of this table contains the ID of a ride, the user's ID that requested it, and the day they requested it.
There may be some ride requests in this table that were not accepted.

Table: AcceptedRides

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| ride_id       | int     |
| driver_id     | int     |
| ride_distance | int     |
| ride_duration | int     |
+---------------+---------+
ride_id is the primary key for this table.
Each row of this table contains some information about an accepted ride.
It is guaranteed that each accepted ride exists in the Rides table.

요구사항

Write an SQL query to report the following statistics for each month of 2020:

The number of drivers currently with the Hopper company by the end of the month ( active_drivers ).
The number of accepted rides in that month ( accepted_rides ).
Return the result table ordered by month in ascending order, where month is the month's number (January is 1 , February is 2 , etc.).

풀이

접근법

처음에 WITH RECURSIVE 구 자체에 GROUP BY 구와 함께 LEFT JOIN 구를 사용해서 문제를 해결하려 했다.

그런데 Recursive CTE (Common Table Expression)에서는 집계 함수(Aggregation Function) 또는 윈도우 함수(Window Function)를 사용하지 못한다는 걸 반환하는 오류 메세지를 통해 알게 되었다.

그래서 단순히 Months 테이블만 WITH RECURSIVE 구를 활용해 임시 테이블로 만들고 해당 테이블에 조건에 따른 COUNT 함수가 적용되어 있는 각각의 ActiveDriversCount 테이블과 AcceptedRidesCount 테이블을 LEFT JOIN 구로 결합하려 했는데 문제는 여러 번 중복되는 레코드로 인해 원하는 값보다 훨씬 큰 값을 얻게 될 수 있다. 예를 들어 아래 테이블과 같다.

문제의 요구사항에 맞춰 active_drivers 필드 값은 결국 이전 월( month )에 대한 누적값을 구해야하기 때문에 Recurcive CTE에 의해 생성된 임시 테이블의 month 필드 값보다 작거나 같은 경우를 LEFT JOIN 구의 조건으로 하여 아래와 같이 결합했을 때 AceeptedRidesCount 테이블 필드의 경우 해당 월( month )의 값만 카운트하는 것이기 때문에 아래 테이블 결과처럼 불필요한 반복이 생기게 되고 결국 원하는 값을 제대로 구할 수 없게 된다.

+-----------+--------------------------+--------------------------+
| cte.month | ActiveDriversCount.month | AcceptedRidesCount.month |
+-----------+--------------------------+--------------------------+
| 1         | 1                        | 1                        |
| 2         | 1                        | 2                        |
| 2         | null                     | 2                        |
| 3         | 1                        | 3                        |
| 3         | null                     | 3                        |
| 3         | 3                        | 3                        |
+-----------+--------------------------+--------------------------+

이를 해결하기 위해서는 앞선 ActiveDriversCount 테이블에 대한 LEFT JOIN 구를 먼저 실행시킨 결과를 month 필드를 기준으로 GROUP BY 구를 실행시켜 이를 서브쿼리로 하고 다시 AcceptedRidesCount 테이블을 LEFT JOIN 구로 결합시키면 되는데 이왕 공통 테이블 표현식을 사용한 김에 이 과정 자체도 나누어 적용하면 좋을 것 같아 전부 Recursive CTE 구 내에 작성하기로 했다.

나의 풀이

그 결과 쿼리는 아래와 같다. 기본적으로 WIRH RECURSIVE 구 내에서 ORDER BY 구는 사용이 불가능하다.

추가적으로 앞서 이야기했던 것처럼 집계 함수와 윈도우 함수 또한 사용 불가능하다는 걸 잊지 말아야겠다.

WITH RECURSIVE Months (month) AS (
    SELECT 1 AS month
    UNION ALL
    SELECT month + 1 AS month
    FROM Months
    WHERE month BETWEEN 1 AND 11
), ActiveDriversCount (month, active_drivers) AS (
    SELECT
        Months.month,
        SUM(IFNULL(ActiveDriversCount.active_drivers, 0)) AS active_drivers
    FROM Months
    LEFT JOIN (
        SELECT
            IF(YEAR(join_date) = 2020, MONTH(join_date), 1) AS month,
            COUNT(driver_id) AS active_drivers
        FROM Drivers
        WHERE YEAR(join_date) <= 2020
        GROUP BY month
    ) AS ActiveDriversCount
    ON Months.month >= ActiveDriversCount.month
    GROUP BY Months.month
), AcceptedRidesCount (month, active_drivers, accepted_rides) AS (
    SELECT
        ActiveDriversCount.month,
        ActiveDriversCount.active_drivers,
        IFNULL(AcceptedRidesCount.accepted_rides, 0) AS accepted_rides
    FROM ActiveDriversCount
    LEFT JOIN (
        SELECT
            MONTH(Rides.requested_at) AS month,
            COUNT(AcceptedRides.ride_id) AS accepted_rides
        FROM Rides
        JOIN AcceptedRides
        USING (ride_id)
        WHERE YEAR(Rides.requested_at) = 2020
        GROUP BY month
    ) AS AcceptedRidesCount
    USING (month)
)

SELECT
    month,
    active_drivers,
    accepted_rides
FROM AcceptedRidesCount
ORDER BY month ASC;