문제

Programmers, 다리를 지나는 트럭

핵심

• 입력의 크기가 $10^4$이라 대략 $O(N^2)$ 이하의 알고리즘을 사용한다.
• 문제를 푸는 시간보다 어떻게 큐로 풀어야 하지? 라는 고민을 더 오래 한 문제이다. 처음에는 큐를 사용하지 않고 임의의 다리 배열을 만들어 지나갈 수 있는 차 무게를 저장한 뒤에 모든 트럭이 지나는 시간을 구했다.
• 먼저 출발한 트럭을 추월할 수 없으므로 선입선출 자료구조인 큐를 선택한다. 큐에 저장하는 값을 {트럭의 무게, 남은 거리}로 두었는데 기존에 다리 배열을 만들어 푼 것과 비교하여 코드의 복잡성이나 시간복잡도가 더 나아지지 않았다. 그 이유는 트럭을 이동시킬 때마다 모든 큐의 원소를 순회하여 남은 거리를 갱신하고 다시 큐를 만드는 작업이 효율적이지 않았기 때문이다.
• 큐에 저장하는 값을 {트럭의 무게, 도착하는 데 걸린 시간}으로 하면 시간에 따라 트럭의 움직임을 계산하는 데 있어 매번 모든 큐를 순회할 필요가 없다. 큐나 스택을 사용해도 변수가 줄어들지 않거나 로직이 조금이라도 단순해지지 않는다면 해당 자료구조를 잘 쓰고 있나 의심할 필요가 있다고 생각한다.

개선

• 직관적으로 접근하여 bridge라는 다리 배열에 다리를 지나갈 수 있는 차 무게를 저장한 뒤에 1초가 흐르면 bridge 배열을 오른쪽으로 한 칸 이동하는 방식으로 구현하였다.

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int bridge[10004] = {0};
    int answer = 0;
    for (int i = 0; i < truck_weights.size(); ++i) {
        // moveCar
        for (int j = bridge_length - 1; j >= 0; --j)
            bridge[j + 1] = bridge[j];
        bridge[0] = 0;
        // sumBridge
        int curWeight = 0;
        for (int j = 0; j < bridge_length; ++j)
            curWeight += bridge[j];
        ++answer;
        // putCar
        if (curWeight + truck_weights[i] <= weight) {
            bridge[0] = truck_weights[i];
        } else {
            while (1) {
                // moveCar
                for (int j = bridge_length - 1; j >= 0; --j)
                    bridge[j + 1] = bridge[j];
                bridge[0] = 0;
                // sumBridge
                int curWeight = 0;
                for (int j = 0; j < bridge_length; ++j)
                    curWeight += bridge[j];
                ++answer;
                // putCar
                if (curWeight + truck_weights[i] <= weight) {
                    bridge[0] = truck_weights[i];
                    break;
                }
            }
        }
    }
    return answer + bridge_length;
}

• 해당 코드를 제출했을 때, 특정 테스트케이스에서 아주 오랜 시간이 걸리는 문제가 발생했다. 코드에서 드러나듯이 다리 길이가 굉장히 길고, 차가 무거워서 각 자동차가 긴 거리를 이동해야 할 때 매번 bridge배열을 복사하는 엄청난 비효율이 발생한다.
• 트럭을 한 칸씩 이동시키는 게 아니라, 한 번에 다리 밖으로 이동할 수 있는 거리를 안다면 최적화할 수 있다. 다음은 이 부분을 최적화한 코드다.

#include <string>
#include <iostream>
#include <vector>
using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int bridge[20004] = {0};
    int answer = 0;
    for (int i = 0; i < truck_weights.size(); ++i) {
        // moveCar
        for (int j = bridge_length - 1; j >= 0; --j)
            bridge[j + 1] = bridge[j];
        bridge[0] = 0;
        // sumBridge
        int curWeight = 0;
        for (int j = 0; j < bridge_length; ++j)
            curWeight += bridge[j];
        ++answer;
        // putCar
        if (curWeight + truck_weights[i] <= weight) {
            bridge[0] = truck_weights[i];
        } else {
            while (1) {
                // findMovement 가장 먼저 출발한 트럭을 다리 밖으로 이동시키는데 필요한 거리
                int findMovement = 0;
                for (int j = bridge_length - 1; j>= 0; --j) {
                    if (bridge[j] != 0) {
                        findMovement = bridge_length - j;
                        break;
                    }
                }
                // moveCar & sumBridge
                int curWeight = 0;
                for (int j = bridge_length - 1; j >= 0; --j) {
                    if (bridge[j] != 0) {
                        bridge[j + findMovement] = bridge[j];
                        bridge[j] = 0;
                        if (j + findMovement < bridge_length) {
                            curWeight += bridge[j + findMovement];
                        }
                    }
                }
                answer += findMovement;
                // putCar
                if (curWeight + truck_weights[i] <= weight) {
                    bridge[0] = truck_weights[i];
                    break;
                }
            }
        }
    }
    return answer + bridge_length;
}

• 두 코드의 시간복잡도 차이는 아래와 같다. 특정 케이스에서 수백배 차이가 난다.
  

코드

시간복잡도

• $O(N)$

C++

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    queue<pair<int, int>> q; // truckWeight, arrivedTime  
    int i = 0;
    int time = 0;
    int curWeight = 0;
    while (i < truck_weights.size()) {
        if (curWeight + truck_weights[i] <= weight) {
            q.push({truck_weights[i], time + bridge_length + 1});
            curWeight += truck_weights[i];
            ++i;
        }
        ++time;
        if (q.front().second == time + 1) {
            curWeight -= q.front().first;
            q.pop();
        }
    }
    int ans = 0;
    while (!q.empty()) {
        ans = q.front().second; q.pop();
    }
    return ans;
}

Java

import java.util.*;

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        Queue<int[]> q = new LinkedList<>(); // truckWeight, arrivedTime
        int i = 0;
        int time = 0;
        int curWeight = 0;
        while (i < truck_weights.length) {
            if (curWeight + truck_weights[i] <= weight) {
                q.add(new int[]{truck_weights[i], time + bridge_length + 1});
                curWeight += truck_weights[i++];
            }
            ++time;
            if (q.peek()[1] == time + 1)
               curWeight -= q.poll()[0];
        }
        int ans = 0;
        while (!q.isEmpty())
            ans = q.poll()[1];
        return ans;
    }
}