SQL | LeetCode 1204. 버스 정원 제한에 따라 탈 수 있는 마지막 사람 구하기

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    | ___          |
+------+----+-----------+--------+--------------+

Queue 테이블은 버스를 기다리는 사람들의 정보를 담고 있습니다. 버스에는 최대 1000kg의 무게 제한이 있습니다. 순서대로 한 명씩 버스에 탑승하지만, 무게 제한을 초과하는 순간 이후 사람들은 탑승할 수 없습니다. 우리는 버스 무게 제한을 넘지 않고 탑승 가능한 마지막 사람의 이름(person_name)을 찾고 싶습니다. 

1. 누적 합 계산: turn 순서대로 weight의 누적 합(total_weight)을 계산합니다.
2. 무게 제한 조건 적용: 누적 합이 1000kg 이하인 사람만 탑승 가능하므로 이를 필터링합니다.
3. 마지막 탑승자 찾기: 누적 합 조건을 만족하는 사람 중 가장 큰 turn 값을 가진 사람이 마지막 탑승자입니다.

WITH OrderedQueue AS (
  SELECT *,
         SUM(weight) OVER (ORDER BY turn) AS total_weight
  FROM Queue
)
SELECT person_name
FROM OrderedQueue
WHERE total_weight <= 1000
ORDER BY turn DESC
LIMIT 1;

• SUM(weight) OVER (ORDER BY turn): turn 기준으로 몸무게를 누적 합산해 total_weight 컬럼으로 생성합니다.
• WHERE total_weight <= 1000: 누적 무게가 1000kg 이하인 경우만 필터링합니다.
• ORDER BY turn DESC LIMIT 1: 탑승 가능한 사람 중 마지막 순서(turn 가장 큰 값)를 가진 사람의 이름을 반환합니다.