문제를 이해하기 부터 어려웠던 문제였습니다.
이 사진이 가장 이해가 잘 되었네요.
문제를 한 번 읽어봤다고 생각하고 설명해 보겠습니다.
- 문제에서 이해해야 할 것은 뒤 차가 앞 차를 만나면 하나의 fleet이 된다는 것입니다. 뒤 차는 추월할 수 없고, 앞 차의 속도를 따라간다고 했기 때문입니다.
사전 지식으로 알아야 할 것은
자료구조는 스택,
거속시 계산식 정도입니다.
stack을 사용하는 이유는 각 자동차를 stack에 넣어놓고 특정조건이 만족할 때 처리해주기 위해서입니다.
자동차의 목적지, 출발지와 속도가 주어졌기 때문에
얼마나 걸리는지 시간을 계산할 수 있습니다.
중학교에서 배웠던 내용.
문제 해결의 핵심은 뒤 자동차가 앞 자동차와 만나는 경우를 어떻게 판단할 것이냐인데요.
시간으로 그 판단이 가능합니다.
만약, 뒤 자동차가 도착지까지 걸리는 시간이 앞 자동차의 시간 보다 작은 경우를 생각해 봅시다.
뒤 자동차가 도착지까지 걸리는 시간은 앞 자동차 보다 작으므로, 뒤 자동차는 도착지까지 가기 전에 앞 자동차를 만나게 됩니다.
그러면 fleet이 만들어지고 문제에서 원하는 조건을 충족하게 됩니다.
이 조건이 몇 번 달성되는지 리턴해주면 되죠.
주의해야할 것은
가장 출발지가 먼 자동차부터 stack에 넣고 전개해야한다는 것입니다.
순차적으로 접근 했을 때 다음 자동차의 상태를 파악할 수 없기 때문입니다.
(A, B, C가 있을 때 B차가 C를 만날지 안 만날지는 알 수 없음)
문제 해결 순서
1. 자동차의 speed와 position을 쌍으로 묶는다.
2. position이 큰 순서대로 정렬
3. 스택에 넣고 스택에 2개 이상의 값이 있고 최근에 들어온 값이 이전 값보다 크면 pop -> fleet이 됐다는 것은 하나가 됐다고 보기 때문에
4. 남은 stack의 값을 return
한 번 샘플로 문제를 해결해보자.
Input 정보
target = 12 - 도착지
position = [10, 8, 0, 5, 3] - 각 자동차의 출발지
speed = [2, 4, 1, 1, 3] - 각 자동차의 속도
class Solution:
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
stack = []
pairs = sorted(list(zip(position, speed)))[::-1]
for p, s in pairs:
stack.append((target - p) / s) # 시간 계산
if len(stack) >= 2 and stack[-2] >= stack[-1]: # 최근 값이 원래 있던 값보다 크다면!
stack.pop() # fleet 합체!
return len(stack)보자마자 zip으로 묶어주고 싶다는 생각이 들었습니다.
sorted 함수로 내림차순 정렬해줍니다.
하나씩 돌면서 조건에 맞는다면(fleet이 된다면) pop 해줍니다.
fleet이 된다면 하나로 보기 때문입니다.
마지막 stack의 남은 값들이 fleet의 개수가 됩니다.
