[ 알고리즘 ] LeetCode 2388. Change Null Values in a Table to the Previous Value

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

본 글은 [ LeetCode ] 2388. Change Null Values in a Table to the Previous Value를 풀고 작성한 글입니다.

문제

테이블

Table: CoffeeShop

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| id          | int     |
| drink       | varchar |
+-------------+---------+
id is the primary key for this table.
Each row in this table shows the order id and the name of the drink ordered. Some drink rows are nulls.

요구사항

Write an SQL query to replace the null values of drink with the name of the drink of the previous row that is not null . It is guaranteed that the drink of the first row of the table is not null .

Return the result table in the same order as the input.

풀이

접근법

총 세 가지 방법을 통해 문제를 해결할 수 있다.

1. LEFT JOIN 구와 GROUP BY 구를 활용한 방법
2. WITH 구를 활용하여 ROW_NUMBER() 윈도우 함수(Window Function)를 사용한 부분을 임시 테이블로 만드는 방법
3. WITH RECURSIVE 구를 활용한 방법

첫 번째 풀이

ROW_NUMBER() 윈도우 함수를 활용하여 해당 부분을 LEFT JOIN 구의 조건으로 사용하고 이후 GROUP BY 구를 통해 가장 최신의 값을 얻어 내서 문제를 해결한다.

SELECT
    id,
    IFNULL(drink, SubTable_drink) AS drink
FROM (
    SELECT
        WithRowNum.id,
        WithRowNum.drink,
        MAX(SubTable.row_num) AS latest_one,
        SubTable.drink AS SubTable_drink
    FROM (
        SELECT
            ROW_NUMBER() OVER() AS row_num,
            id,
            drink
        FROM CoffeeShop
    ) AS WithRowNum
    LEFT JOIN (
        SELECT
            ROW_NUMBER() OVER() AS row_num,
            id,
            drink
        FROM CoffeeShop
    ) AS SubTable
    ON (
        WithRowNum.drink IS NULL
        AND
        WithRowNum.row_num > SubTable.row_num
        AND
        SubTable.drink IS NOT NULL
    )
    GROUP BY WithRowNum.id
) AS Result;

두 번째 풀이

앞선 첫 번째 풀이에서 공통으로 사용되는 테이블을 WITH 구를 활용하여 임시 테이블로 만들어서 사용한다.

WITH WithRowNum (row_num, id, drink) AS (
    SELECT
        ROW_NUMBER() OVER() AS row_num,
        id,
        drink
    FROM CoffeeShop
)

SELECT
    id,
    IFNULL(drink, SubTable_drink) AS drink
FROM (
    SELECT
        WithRowNum.id,
        WithRowNum.drink,
        MAX(SubTable.row_num) AS latest_one,
        SubTable.drink AS SubTable_drink
    FROM WithRowNum
    LEFT JOIN WithRowNum AS SubTable
    ON (
        WithRowNum.drink IS NULL
        AND
        WithRowNum.row_num > SubTable.row_num
        AND
        SubTable.drink IS NOT NULL
    )
    GROUP BY WithRowNum.id
) AS Result;

세 번째 풀이

WITH RECURSIVE 구를 활용하여 내부적으로 JOIN 구를 재귀적으로 수행하게 해 문제를 해결한다.

WITH RECURSIVE WithRowNum (row_num, id, drink) AS (
    SELECT
        ROW_NUMBER() OVER() AS row_num,
        id,
        drink
    FROM CoffeeShop
), Result (row_num, id, drink) AS (
    SELECT
        row_num,
        id,
        drink
    FROM WithRowNum
    WHERE row_num = 1
    UNION ALL
    SELECT
        WithRowNum.row_num,
        WithRowNum.id,
        IFNULL(WithRowNum.drink, Result.drink) AS drink
    FROM Result
    JOIN WithRowNum
    ON Result.row_num = WithRowNum.row_num - 1
)

SELECT id, drink
FROM Result;