Car Fleet
- 문제
- 도로는 1차선이기 때문에 추월할 수 없다
- 겹쳐질 수 있고, 겹쳐진다면 더 느린 속도로 이동하는 차의 속도에 맞춰진다
- 생각해볼 수 있는 것
-
임의의 차량 A를 기준으로 임의의 차량 B를 비교한다면 4가지의 경우를 생각할 수 있다
A. 포지션 뒤, 스피드 느림 B. 포지션 앞, 스피드 느림 C. 포지션 뒤, 스피드 빠름 D. 포지션 앞, 스피드 빠름 1 2
포지션 뒤 : 도착지에서 더 멀다 포지션 앞 : 도착지에서 더 가깝다
- A, D는 검사할 필요가 없이 둘은 무조건 따로 오게 된다
- B, C는 검사가 필요하다
- 목적지를 기준으로 둘이 따로 도착하는지, 같이 도착하는지
- ex) Target : 15, A → Pos : 10, Speed : 1, B → Pos : 5, Speed : 7
- ex) Target : 11, A → Pos : 10, Speed : 1, B → Pos : 5, Speed : 3
- 목적지를 기준으로 둘이 따로 도착하는지, 같이 도착하는지
-
- 풀이
- 각 차량을 다 비교한다면 N은 10^5 이기에 시간초과
- 힌트를 기준으로 차량은 ‘추월’할 수 없기에 도착지에 가까운 차량부터 검사를 해준다
- 도착지에 가까운 차량부터 각 차량이 언제 도착하는지 저장을 해준다
- ‘가장 느리게 도착하는 차량’을 기준으로 검사를 진행하면 답을 구할 수 있다
-
포지션이 뒤에 있는데 더 빨리 도착한다는 뜻은?
→ 포지션이 앞에 있는 차량을 만나서 같이 온다
-
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int carFleet(int target, int[] position, int[] speed) {
float[] times = new float[target];
for (int i = 0; i < position.length; i++)
times[position[i]] = (float) (target - position[i]) / speed[i];
int answer = 0;
float before = 0;
for (int i = target - 1; i >= 0; i--) {
float now = times[i];
if (now > before) {
before = now;
answer++;
}
}
return answer;
}
}
