프로그래머스_코딩테스트연습_스택/큐_다리를지나는트럭

♠ 소스코드

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

typedef pair<int, int> info; //시작 시각, 무게
int solution(int bridge_length, int weight, vector<int> truck_weights) {

    int answer = 0;

    int num_total = truck_weights.size(); //전체 트럭 대수
    int next_truck_index = 1; //다음 트럭 번호
    int num_crossed = 0; //다리 건넌 트럭 대수
    int weight_on_bridge = 0; //다리 위 트럭 무게 총합
    int time_now=0; //현재 시각
    deque<info> trucks_on_bridge; //다리 위 트럭

 

    //1초일 때 상황
    time_now = 1;
    weight_on_bridge = truck_weights[0];

    trucks_on_bridge.push_back(make_pair(time_now, truck_weights[0]));

    //cout << trucks_on_bridge[0].first << "\t" << trucks_on_bridge[0].second << endl; //for debug

 

    //반복

    while(num_total != num_crossed) //종료조건
    {
        //시간 흐름
        time_now++;
        //cout << endl << time_now << "초: ";
        //현재시각 - 시작 시각 == bridge_length 이면 트럭 나감.
        if(time_now - trucks_on_bridge[0].first == bridge_length)
        {

            weight_on_bridge -= trucks_on_bridge[0].second;

            //cout << trucks_on_bridge[0].second <<"트럭 나감 현재 weight: " << weight_on_bridge << "      ";
            trucks_on_bridge.pop_front();

            num_crossed++;
        }
        //next_truck_index > num_total 이면 마지막 트럭이 더 이상 건널 트럭 없음.
        if(next_truck_index < num_total)
        {
            //무게총합 + 다음 트럭 무게 < 무게 한계 이면 트럭 추가.
            if(weight_on_bridge + truck_weights[next_truck_index] <= weight)
            {
                weight_on_bridge += truck_weights[next_truck_index];
                //cout << truck_weights[next_truck_index] << " 트럭 추가 현재 weight: " << weight_on_bridge << "      ";
                trucks_on_bridge.push_back(make_pair(time_now, truck_weights[next_truck_index++]));
            }
        }
        
    }
    answer = time_now;
    return answer;
}

 

♠ 고찰

▶ time complexity

while loop를 몇 번 반복실행하는 지가 시간복잡도에 영향을 미친다.

입력되는 트럭의 무게와 다리가 견디는 무게에 따라 반복실행 횟수가 달라진다.

최선의 경우, 만약 트럭이 연속해서 들어오고 나가는 것을 반복한다면 O(N+bridge_length) = O(N)

최악의 경우, 만약 트럭이 나가야지만 다음 트럭이 들어올 수 있다면 O(bridge_length*N + 1) = O(N) 이다.

 

▶ 알고리즘

변수 설명:

num_total : 전체 트럭 대수

next_truck_index : 다음 트럭 번호 
num_crossed : 다리 건넌 트럭 대수 
weight_on_bridge : 다리 위 트럭 무게 총합 
time_now : 현재 시각 
trucks_on_bridge : 다리 위 트럭을 담는 큐 ( 뒤에서 넣고 앞에서 빼기 위해 deque를 사용하였다. )

큐에 트럭 정보는 pair를 이용하여 시작 시각과 트럭의 무게를 담는다.

 

알고리즘:

1) 1초일 때 무조건 첫 트럭이 다리에 진입한다.

weight_on_bridge에 첫 번째 트럭의 무게를 더해주고,

trucks_on_bridge에 첫 번째 트럭에 대한 정보<시작 시각(=1), 트럭 무게>를 담는다.

2) while문으로 반복실행

종료조건 : 전체 트럭 대수와 다리를 건넌 트럭 대수가 같으면 종료.

while문 한 번 실행때마다 시간이 흘렀다고 하여 time_now +1

다리에서 빠져나가는 트럭이 있는지 우선 검사.

2-1) 현재시각 - 시작 시각 == bridge_length 이면 트럭이 나가도록 실행.

2-2) 새로 건널 트럭이 남아있는지 검사

      ( 다음 트럭 번호 > 전체 트럭 대수 이면 더 이상 건널 트럭이 없음을 의미. )

      && 새로 다리에 진입할 트럭이 있는지 검사.

            ( 무게총합 + 다음 트럭 무게 < 무게 한계 이면 트럭 추가. )

while문을 빠져나온 후 시간이 모든 트럭이 다리를 건너는 데 걸린 시간이므로 return