[SQL_Q] 1204. Last Person to Fit in the Bus

https://leetcode.com/problems/last-person-to-fit-in-the-bus/description/

문제

Table: Queue

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| person_id   | int     |
| person_name | varchar |
| weight      | int     |
| turn        | int     |
+-------------+---------+
person_id column contains unique values.
This table has the information about all people waiting for a bus.
The person_id and turn columns will contain all numbers from 1 to n, where n is the number of rows in the table.
turn determines the order of which the people will board the bus, where turn=1 denotes the first person to board and turn=n denotes the last person to board.
weight is the weight of the person in kilograms.
 

There is a queue of people waiting to board a bus. However, the bus has a weight limit of 1000 kilograms, so there may be some people who cannot board.

Write a solution to find the person_name of the last person that can fit on the bus without exceeding the weight limit. The test cases are generated such that the first person does not exceed the weight limit.

Note that only one person can board the bus at any given turn.

The result format is in the following example.

 

Example 1:

Input: 
Queue table:
+-----------+-------------+--------+------+
| person_id | person_name | weight | turn |
+-----------+-------------+--------+------+
| 5         | Alice       | 250    | 1    |
| 4         | Bob         | 175    | 5    |
| 3         | Alex        | 350    | 2    |
| 6         | John Cena   | 400    | 3    |
| 1         | Winston     | 500    | 6    |
| 2         | Marie       | 200    | 4    |
+-----------+-------------+--------+------+
Output: 
+-------------+
| person_name |
+-------------+
| John Cena   |
+-------------+
Explanation: The folowing table is ordered by the turn for simplicity.
+------+----+-----------+--------+--------------+
| Turn | ID | Name      | Weight | Total Weight |
+------+----+-----------+--------+--------------+
| 1    | 5  | Alice     | 250    | 250          |
| 2    | 3  | Alex      | 350    | 600          |
| 3    | 6  | John Cena | 400    | 1000         | (last person to board)
| 4    | 2  | Marie     | 200    | 1200         | (cannot board)
| 5    | 4  | Bob       | 175    | ___          |
| 6    | 1  | Winston   | 500    | ___          |
+------+----+-----------+--------+--------------+

내 쿼리

with sub as (
SELECT
person_name, sum(weight) over(order by turn) weight
FROM Queue
)
select person_name
FROM sub
where weight <= 1000
order by weight DESC
limit 1

다른 사람 쿼리

SELECT person_name
from (SELECT person_name,turn,sum(weight) 
      over (order by turn) AS cum 
      FROM queue) p1
where cum<=1000 
order by turn DESC limit 1;

다른 사람 쿼리와 비교한 내 쿼리의 문제점

1. 가독성 문제
   • weight라는 기존 컬럼명과 동일한 이름을 SUM(weight) 결과에도 사용했는데, 혼동을 유발할 수 있다. 누적연산에서는 cum(cumulative) 을 자주 쓴다고 하니 활용하자.

2. 성능 문제
   • 인덱스 활용성
     최종 정렬 기준이 내 쿼리에서는 누적 weight에 대한 정렬이므로, 인덱스가 활용되지 않음.(정렬 연산이 필요)
     반면, 다른 사람 쿼리는 최종 정렬이 turn DESC이므로 기존 primary key인 turn 인덱스를 그대로 활용 가능.

수정된 쿼리

with sub as (
SELECT
person_name, turn, sum(weight) over(order by turn) cum_weight
FROM Queue
)
select person_name
FROM sub
where cum_weight <= 1000 
order by turn DESC
limit 1

order by weight DESC 로 새로 계산하는 것보다 turn에 인덱스가 있다고 가정할 때, turn 기준으로 서브쿼리에서 누적합을 계산하고, turn DESC로 정렬해서 가져오는 전략이다.

turn은 기존 인덱스가 있는 컬럼이므로, 인덱스 스캔으로 정렬 생략이 가능하다.