Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 자동차 함대(Car Fleet) 문제: 스택 활용 알고리즘

문제 개요

일차선 도로를 따라 같은 목적지를 향해 달리는 N대의 자동차가 있다고 가정해 보겠습니다. 목적지까지의 거리는 'target'마일이며, 각 자동차 i는 시간당 마일(mph) 단위의 일정한 속도 speed[i]와, 도로 위에서 목적지 방향으로의 초기 위치 position[i]를 가집니다.

자동차는 앞차를 절대 추월할 수 없지만, 앞차를 따라잡아 같은 속도로 바짝 붙어 주행하는 것은 가능합니다. 이때 두 차량 사이의 거리는 무시되며, 동일한 위치에 있는 것으로 간주합니다. 자동차 함대(car fleet)란 같은 위치에서 같은 속도로 주행하는 하나 이상의 자동차 집합을 의미합니다. 만약 어떤 차가 목적지 지점에서 정확히 함대를 따라잡았다면, 그 차 역시 해당 함대의 일부로 간주됩니다. 이 문제의 목표는 최종적으로 목적지에 도착하는 함대의 개수를 구하는 것입니다.

예제로 이해하기

예를 들어 target이 12이고, position이 [10, 8, 0, 5, 3], speed가 [2, 4, 1, 1, 3]이라면 결과값은 3이 됩니다.

  • 위치 10과 8의 차량 — 12 지점에서 서로 만나 하나의 함대를 이룹니다.
  • 위치 0의 차량 — 어떤 차량도 따라잡지 못하므로 단독으로 하나의 함대가 됩니다.
  • 위치 5와 3의 차량 — 6 지점에서 서로 만나 하나의 함대를 이룹니다.

해결 전략

이 문제는 정렬과 스택(stack)을 조합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 차량이 목적지에 도달하는 데 걸리는 시간을 계산한 뒤, 뒤따르던 차량이 앞차를 도착 시점 이전 또는 같은 시점에 따라잡는 경우 두 차량을 하나의 함대로 병합하는 것입니다.

구체적인 알고리즘 단계는 다음과 같습니다.

  1. (위치, 속도) 쌍을 저장할 배열 v를 만들고, n을 위치 배열 p의 크기로 설정합니다.
  2. i를 0부터 n-1까지 반복하면서 (p[i], s[i]) 쌍을 v에 삽입합니다.
  3. 결과 변수 ret을 n으로 초기화합니다. 처음에는 모든 차량이 각각 독립적인 함대라고 가정하는 것입니다.
  4. v 배열을 위치 기준으로 오름차순 정렬합니다. 즉, 목적지에서 가장 먼 차량부터 순서대로 처리합니다.
  5. 스택 st를 선언합니다.
  6. i를 0부터 n-1까지 반복하면서 다음을 수행합니다.
    • temp := (t − v[i].first) / v[i].second — 현재 차량의 목적지 도착 예상 시간입니다.
    • 스택이 비어 있지 않고 스택의 최상단 값이 temp 이하인 동안 다음을 반복합니다.
      • ret을 1 감소시킵니다. 두 차량이 하나의 함대로 합쳐졌음을 의미합니다.
      • 스택의 최상단 요소를 제거합니다.
    • temp를 스택에 삽입합니다.
  7. ret을 반환합니다.

여기서 스택의 최상단 값이 temp 이하라는 것은, 현재 차량보다 뒤에 출발한 차량이 현재 차량(또는 그 함대)에 도착 전이나 도착 시점에 따라잡는다는 뜻입니다. 따라서 두 차량은 하나의 함대로 병합되며, 함대의 개수를 나타내는 ret이 감소합니다. 이 과정을 모든 차량에 대해 수행하면 최종 함대 수를 얻을 수 있습니다. 시간 복잡도는 정렬이 지배하므로 O(n log n), 공간 복잡도는 O(n)입니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int carFleet(int t, vector<int>& p, vector<int>& s) {
        vector<pair<double, double>> v;
        int n = p.size();
        for(int i = 0; i < n; i++){
            v.push_back({p[i], s[i]});
        }
        int ret = n;
        sort(v.begin(), v.end());
        stack<double> st;
        for(int i = 0; i < n; i++){
            double temp = (t - v[i].first) / v[i].second;
            while(!st.empty() && st.top() <= temp){
                ret--;
                st.pop();
            }
            st.push(temp);
        }
        return ret;
    }
};
int main(){
    vector<int> v1 = {10, 8, 0, 5, 3};
    vector<int> v2 = {2, 4, 1, 1, 3};
    Solution ob;
    cout << ob.carFleet(12, v1, v2);
}

실행 결과

입력:

12
[10,8,0,5,3]
[2,4,1,1,3]

출력:

3

출력값 3은 앞서 살펴본 예제 설명과 정확히 일치합니다. 위치 10·8의 차량이 하나의 함대를, 위치 5·3의 차량이 또 다른 함대를, 위치 0의 차량이 마지막 함대를 이루기 때문입니다.