[문제풀이] Leet code - Last Person to Fit in the Bus

 

출처

 

문제

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.

 

문제에 대한 해석

첫번째 탄 사람부터 1000kg을 넘지 않는 마지막 사람의 이름

 

풀이(MYSQL)

select turn, person_name,weight,
sum(weight)over() as 'weight'
from Queue
order by turn

윈도우 절에 순서(order by)를 작성하지 않으면 전체가 반영된 값(전체합)으로 계산된다

 

-- 정답1.
with base as ( -- 탑승순으로 몸무게 누적합 계산
    select turn, person_name,weight,
    sum(weight)over(order by turn) as 'cum'
    from Queue 
    order by turn
)
select person_name -- 누적몸무게가 1000 이하일때 마지막 사람 이름
from base
where cum <= 1000
order by turn desc
limit 1

 

-- 정답2
SELECT 
    q1.person_name
FROM Queue q1 JOIN Queue q2 ON q1.turn >= q2.turn
GROUP BY q1.turn
HAVING SUM(q2.weight) <= 1000
LIMIT 1

 

FROM Queue q1 JOIN Queue q2 ON q1.turn >= q2.turn

: 본인을 포함하여 본인 이후 탑승한 사람들과 조인

1번 탑승자는 1~6번 탑승자와 조인

2번탑승자는 1번을 제외한 2~6번탑승자까지 조인

 

GROUP BY q1.turn

HAVING SUM(q2.weight) <= 1000

ORDER BY SUM(q2.weight) DESC

 

t1으로 그룹화하면 t1을 포함한 이전사람들까지 무게를 합칠때

그 합쳐진 무게가 1000이하인 경우 필터링