물류창고 화물 리프트

문제

물류창고에는 화물 전용 리프트가 한 대 있습니다. 리프트는 start층에서 상행 방향 으로 대기를 시작하며, 화물 운송 요청 목록 requests를 모두 처리해야 합니다.

requests[i] = [from, to]는 요청 i 의 화물을 from층에서 싣고 to층에서 내려야 한다는 뜻입니다. 요청의 방향은 to > from이면 상행, to < from이면 하행입니다. 리프트에는 화물이 동시에 최대 cap개까지만 실릴 수 있습니다(요청 1건 = 화물 1개).

리프트는 한 번에 한 층씩 이동하며, 매 층에 도착할 때마다 다음을 순서대로 수행합니다.

1. 하차: 싣고 있는 화물 중 목적지(to)가 현재 층인 화물을 모두 내립니다. 같은 층에서 여러 개를 동시에 내리면 요청 번호가 작은 것부터 완료된 것으로 기록합니다.
2. 승차: 아직 싣지 않은 대기 요청 중 출발지(from)가 현재 층이고 요청의 방향이 리프트의 현재 진행 방향과 같은 것을 요청 번호가 작은 순서로 싣습니다. 단, 싣는 도중 화물이 cap개가 되면 그 층에서는 더 싣지 않습니다. (하차가 승차보다 먼저이므로, 내린 만큼 자리가 비면 같은 층에서 바로 실을 수 있습니다.)

리프트는 다음 규칙으로 이동 방향을 정합니다.

• 현재 진행 방향 앞쪽(현재 층 제외)에 처리할 일 이 하나라도 있으면 그 방향으로 한 층 이동합니다. 처리할 일이란
  • 싣고 있는 화물의 목적지 층, 또는
  • 아직 싣지 않은 대기 요청의 출발지 층 (요청의 방향과 무관) 이 진행 방향 앞쪽에 있는 경우를 말합니다.
• 앞쪽에 처리할 일이 없으면 그 자리에서 방향을 반전 합니다. 방향을 반전한 직후, 현재 층에서 새 방향과 일치하는 대기 요청이 있으면 (용량이 허용하는 한) 즉시 싣고 나서 이동을 시작합니다. 방향 반전 자체는 이동 층수에 포함되지 않습니다.

모든 요청이 완료될 때까지 시뮬레이션했을 때, 리프트가 이동한 총 층수 와 요청이 완료된 순서(요청 번호 배열) 를 구하는 solution(start, cap, requests) 함수를 작성하세요.

반환값은 길이 2의 배열 [총 이동 층수, 완료 순서 배열]입니다. 요청이 하나도 없으면 [0, []]을 반환합니다.

예시

예시 1 설명: 1층에서 상행 출발 → 2층에서 요청 0(2→5) 승차 → 3층의 요청 1은 하행이라 태우지 않음 → 5층에서 요청 0 하차. 위쪽에 일이 없으므로 방향 반전 후 요청 2(5→2) 승차 → 3층에서 요청 1(3→1) 승차 → 2층에서 요청 2 하차 → 1층에서 요청 1 하차. 총 이동 층수는 1→5(4층) + 5→1(4층) = 8, 완료 순서는 [0, 2, 1].

예시 3 설명: 같은 층(3층)의 하행 요청 3건, 용량 2. 시작 시 상행이지만 위쪽에 일이 없어 즉시 반전 후 요청 0, 1만 승차(용량 초과로 요청 2는 대기) → 1층에서 하차 → 남은 요청 2를 실으러 3층까지 상행 후 다시 반전·승차 → 1층 하차. 총 3→1(2) + 1→3(2) + 3→1(2) = 6.

제약 조건

• 1 <= start <= 100, 모든 층 번호는 1 이상 100 이하의 정수
• 1 <= cap <= 10
• 0 <= requests.length <= 200
• 각 요청은 from !== to
• 같은 층에 여러 요청이 있을 수 있고, 완전히 동일한 [from, to] 요청이 중복될 수 있다

시간 복잡도 목표: O(P × F × N) — P는 왕복 횟수, F는 층 범위, N은 요청 수 (제약 내에서 층 단위 시뮬레이션이면 충분)