리트코드 : 1204. Last Person to Fit in the Bus

리트코드 : 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.

The result format is in the following example.

 

문제 풀이

MySQL

with ordered as (
    select *, sum(weight) over (order by turn) as total_weight
    from queue
)

select person_name
from ordered
where total_weight <= 1000
order by total_weight desc
limit 1

• 윈도우 함수를 사용해서 문제풀이.
• weight에 누적합을 적용하고 대기 순서 turn으로 정렬을 걸어준다.
• 누적합이 1000이 넘지 않는 사람들의 쿼리를 역순을 정렬하고 하나 뽑아주기.

Pandas

import pandas as pd

def last_passenger(queue: pd.DataFrame) -> pd.DataFrame:
    ordered = queue.sort_values(by='turn')
    ordered['total_weight'] = ordered['weight'].cumsum()
    answer = ordered[ordered['total_weight']<=1000]
    return answer[['person_name']].tail(1)

• SQL처럼 한 번에 정렬 + 누적합은 불가능해서 두 번 나눠서 풀이.
• 정렬 이후에 cumsum으로 누적합을 구해준다.
• iloc대신 tail 또는 head를 사용해서 앞에 있는 데이터플레임을 추출하기.

 

코멘트

• .