[알고리즘문제] 프로그래머스 다리를 지나는 트럭

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

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

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int time = 0, total_weight = 0, entered = 0, cCount = 0;
    queue<int> info;

    while (1) {
    	time++;
        if (time != 1) {
            if(time == info.front()){
                info.pop();
                total_weight -= truck_weights[cCount];
                cCount++;
            }
        }

        if (truck_weights.size() > entered) {
            if ((total_weight + truck_weights[entered]) > weight) {
                time = info.front();
                swi = true;
                continue;
            }
            info.push(time + bridge_length);
            total_weight += truck_weights[entered];
            entered++;
        }

        if (info.empty()) {
            break;
        }
    }

    return time;
}

트럭이 다리에 진입한 시점으로부터, 탈출할 시간을 담는 Queue를 생성하여 반복하며 각 조건을 계산하고 마지막으로 큐의 내용이 비어있을 경우 루프를 탈출하는 방법이다. 매 반복문 마다 조건을 확인하므로 비효율적인 코드이기도 하다.

 

 

#include<iostream>
#include<queue>
#include<vector>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int time = 0, total_weight = 0, entered = 0, cCount = 0;
    bool swi = false;
    queue<int> info;

    while (1) {
        if (swi == true) {
            swi = false;
        }
        else {
            time++;
        }
        if (time != 1) {
            if(time == info.front()){
                info.pop();
                total_weight -= truck_weights[cCount];
                cCount++;
            }
        }

        if (truck_weights.size() > entered) {
            if ((total_weight + truck_weights[entered]) > weight) {
                time = info.front();
                swi = true;
                continue;
            }
            info.push(time + bridge_length);
            total_weight += truck_weights[entered];
            entered++;
        }

        if (info.empty()) {
            break;
        }
    }

    return time;
}

위와같은 식으로 time이 증가하는 조건을 하나 더 추가하였다.

입력될 트럭과 기존 다리위의 트럭의 합이 다리의 최대중량보다 클 경우에는 time을 1 증가시키는 것이 아닌 큐에 입력되어있는 트럭이 탈출할 시간을 time에 할당하는 방식으로 타임을 건너뛰는 방식으로 소스코드를 수정했다.