[리트코드] |1204. Last Person to Fit in the Bus; 인라인뷰, SUM OVER 누적합
https://leetcode.com/problems/last-person-to-fit-in-the-bus/description/
1. Problem
버스 승차 정원이 몸무게 총합 1,000kg으로 제한되어 있을 때, 승차 순서(turn)에 따라 마지막으로 버스에 탈 수 있는 사람의 이름을 찾아야 한다.
- 핵심 난관: 각 행은 독립적인 데이터이지만, 승차 여부는 **'나보다 먼저 탄 사람들의 무게 합'**에 의존한다. 즉, 행과 행 사이의 연속적인 계산이 필요하다.
2. Solution: 인라인 뷰와 SUM() OVER()의 결합
윈도우 함수를 이용해 순차적인 누적합을 구한 뒤, 필터링과 정렬을 통해 최종 승차자를 특정한다.
3. Takeaway: 왜 윈도우 함수인가? (객관적 분석)
- GROUP BY vs OVER():
- GROUP BY는 여러 행을 하나의 요약된 행으로 압축한다. 하지만 이 문제는 모든 승객의 '현재 상태'를 유지하면서 계산해야 하므로, 행의 개수를 유지하며 집계값을 추가하는 윈도우 함수가 정답이다.
- SUM(weight) OVER (ORDER BY turn)의 원리:
- ORDER BY turn이 포함되는 순간, SQL은 첫 번째 행부터 현재 행까지의 범위를 지정하여 합계를 구한다. 이것이 바로 '누적합(Running Total)'을 만드는 표준 방식이다.
- 데이터 필터링의 순서:
- 누적합은 SELECT 절에서 계산되므로, WHERE 절에서 바로 사용할 수 없다. 따라서 반드시 **인라인 뷰(서브쿼리)**를 통해 누적합이 계산된 테이블을 먼저 정의한 뒤 바깥에서 필터링해야 한다.
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 | ___ |
+------+----+-----------+--------+--------------+
1. 정답
누적합 + 조건 + 마지막 값을 묻는, 전형적인 SQL 감각 테스트
turn 순서대로 weight 누적합을 구한 뒤,
누적합 ≤ 1000 인 사람 중 turn이 가장 큰 사람
1. 정답 쿼리
SELECT person_name
FROM (
SELECT person_name,
SUM(weight) OVER (ORDER BY turn) AS total_weight # turn 순서대로 누적합
FROM Queue
) t
WHERE total_weight <= 1000 # 탈 수 있는 사람만 필터
ORDER BY total_weight DESC # “마지막 사람” 고르기
LIMIT 1;
# GROUP BY ❌ (행 단위 문제임)