SQL > LeetCode 1204. Last Person to Fit in the Bus (MySQL)

문제

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.

 

사람들이 버스를 기다리고 있다. 그런데 버스에는 1000 kilogram까지만 탑승이 가능하다.

탑승이 가능한 인원들 중에 가장 마지막 인원의 이름을 출력해야한다.

 

테이블 & 예제

[Queue]

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| person_id   | int     |
| person_name | varchar |
| weight      | int     |
| turn        | int     |
+-------------+---------+

 

[Examples]

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

 

풀이

오늘 풀이는 두가지 입니다~

풀이는 누적합을 계산하여 풀이하는 방식입니다.

1. CTE & SUM OVER 사용해서 누적합 계산하기

SUM OVER.. 실은 이게 누적합을 구해주는지 몰랐습니다. 단순하게 행의 범위만 지정하는 줄 알았는데 SUM과 함께 쓰는 방식은 처음 접해서 그랬던 것 같습니다. 여튼 제가 참고한 포스팅을 가져왔습니다. https://gent.tistory.com/511

[MSSQL] 순차적 누적 합계 구하기 (SUM OVER)

참고하시면 좋을듯 합니다.

여튼 이를 이용해서 누적합을 갖는 CTE를 만들었습니다.

WITH CTE AS(
    SELECT *,
        SUM(weight) OVER (ORDER BY turn) AS Total_weight 
    FROM Queue
)

 

그리고 나서 WHERE절과 ORDER BY를 이용해서 조건들을 걸고 가장 마지막 1개의 행만 출력해야했기에 Limit를 걸었습니다.

WITH CTE AS(
    SELECT *,
        SUM(weight) OVER (ORDER BY turn) AS Total_weight 
    FROM Queue
)
SELECT person_name
FROM CTE
WHERE Total_weight <=1000
ORDER BY Total_weight DESC
limit 1

 

 

2. 자기자신을 JOIN

왜 이걸 가져왔냐면 JOIN 시에 ON 부분에 무조건 등호가 들어갈것이라는 고정관념을 가져버렸는데 바로 부수어준(?) 풀이이기에 가져왔습니다. 코드는 아래와 같습니다.

SELECT 
    q1.person_name
FROM Queue q1 JOIN Queue q2 ON q1.turn >= q2.turn
GROUP BY q1.turn
HAVING SUM(q2.weight) <= 1000
ORDER BY SUM(q2.weight) DESC
LIMIT 1

 

JOIN을 하는 부분이외에 다른 부분들은 CTE와 비슷합니다.

q1에 대해서 턴이 낮은 값들을 일단 몽땅 가져오고 SUM으로 조건을 파악합니다.