[프로그래머스 - 다리를 지나는 트럭 / C++]

programmers.co.kr/learn/courses/30/lessons/42583

코딩테스트 연습 - 다리를 지나는 트럭

 

위의 표로 문제를 이해하는 것이 도움이 많이 됐다. 예제로 주어진 테스트 케이스만 모두 성공시키니, 히든케이스까지 모두 풀렸다. 😆

우선 다리를 하나의 deque라고 생각하고, 대기하고 있는 트럭은 deque의 뒤로 push_back 하고, 다리를 모두 건넌 트럭은 deque의 앞으로 pop_front 한다면 문제가 간단해질 것이라고 판단했다.

 

모든 트럭이 다리를 걸리는데 걸리는 시간을 측정해 return 하는 문제니, answer로 초를 세주는 것으로 결정했다.

while문을 실행시키고 answer++을 통해 초를 counting 해주었으며, 만일 다리를 모두 건넌 completed_truck의 개수가 트럭의 개수와 같아진다면 break를 통해 while 문을 빠져나왔다.

 

다리에 대기하고 있던 트럭이 들어가는 조건은

 

1. 다리에 있는 트럭의 수(bridge.size())가 다리가 수용할 수 있는 트럭의 수, 즉 다리의 길이(bridge_length)보다 작아야 한다

2. [현재 다리에 있는 총 트럭 무게의 합 + 다음 다리에 들어올 트럭의 무게] 는 트럭이 수용할 수 있는 무게, 즉 파라미터로 주어진 weight보다 작거나 같아야 한다.

3. truck의 index를 카운팅하는 truck_index의 값이 트럭의 개수(num_truck)보다 작아야한다.

 

등이 있다.

 

위와 같은 조건을 고려한 후에는,후에는 현재 트럭이 다리에 있었던 시간을 update해주어야 한다. 처음 풀었을 때는 이 경우를 고려하지 않아서 테스트 케이스가 지속적으로 틀렸다. 이보다 더 간단한 방법을 찾고자 노력하였지만, 다리의 길이 및 트럭의 개수가 10000이하인 것을 고려하여 for문을 통해 초를 지속적으로 카운팅 해주었다.

 

만일 다리 위, 맨 앞에 있는 트럭이 다리에 머문 시간이 bridge_length와 같다면 트럭은 다리를 빠져나와야 했기 때문에 pop_front를 통해 해당 과정을 수행해 주었다.

 

completed_truck에는 다리를 빠져나온 트럭을, total_truck 다리를 건너는 트럭 무게의 합을 기억하고 있는 역할을 수행했다.

초를 카운팅 해주는 부분을 최대한 아끼려고 다른 방식을 생각하다보니 오랜 시간이 걸려 문제를 푼 듯 싶다... 😱

 

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

deque<pair<int, int>> bridge;

int solution(int bridge_length, int weight, vector<int> truck_weights)
{
    int answer = 0;
    int total_truck = 0;
    int completed_truck = 0;
    int index_truck = 0;
    int num_truck = truck_weights.size();
    while (true) {
        answer++;
        if (completed_truck == num_truck)
            break;
        if (bridge.size() < bridge_length && (total_truck + truck_weights[index_truck]) <= weight && index_truck < num_truck) {
            bridge.push_back({ truck_weights[index_truck], 1 });
            total_truck += truck_weights[index_truck++];
        }
        if (bridge.front().second >= bridge_length) {
            int ct = bridge.front().first;
            bridge.pop_front();
            completed_truck++;
            total_truck -= ct;
        }
        for (int i = 0; i < bridge.size(); i++) {
            bridge[i].second++;
        }
    }
    return answer;
}