[Programmers, C++]#Level2_다리를 지나가는 트럭, 선형 자료구조, queue 컨테이너, deque 컨테이너

#1. 문제

프로그래머스

 

---

 

#2. 풀이

 

1. queue

[Basic C++] #67_queue

C++의 STL에서 제공하는 queue 컨테이너는 선입 선출 방식으로 동작하는 순차 컨테이너로, 한쪽 끝에서 삽입 작업, 다른 한쪽 끝에서는 제거 작업만 이루어지는 컨테이너입니다.

 

2. deque

[Basic C++] #68_deque

C++의 STL에서 제공하는 deque 컨테이너는 양쪽 끝에서 삽입/삭제/접근 작업이 가능한 순차 컨테이너입니다.

 

3. 나갈 트럭은 큐에서 손! 들어올 트럭은 덱에서 손!

1. 먼저, 각 트럭의 인덱스를 queue 컨테이너에 순차적으로 삽입해줍니다.
2. 큐가 빌 때까지 순회하며, 큐에서는 현재 다리에 트럭이 올라탈 수 있는지 확인하고, 덱에서는 현재 다리에 올라가 있는 트럭들 중 가장 먼저 올라탄 트럭이 지금 다리를 나갈 것인지 확인합니다.

 

---

 

#3. 코드

/*
    @링크: https://school.programmers.co.kr/learn/courses/30/lessons/42583
    @문제: 일차선 다리를 정해진 순서로 건널 때 모든 트럭이 다리를 건너는 최소 시간
    @설명
        1. queue 컨테이너, deque 컨테이너 활용
        2. queue 컨테이너만 활용
*/
#include <string>
#include <vector>
#include <queue>
#include <deque>

using namespace std;

typedef pair<int,int> p;

int solution(int bridge_length, int weight, vector<int> truck_weights) 
{
    //@트럭 목록
    queue<int> q;
    for(int i=0; i<(int)truck_weights.size(); ++i)
        q.push(i);
    //@다리
    deque<p> dq;
    //@시간
    int time = 1;
    //@다리의 현재 총 무게
    int curWeight = 0;

    //@트럭이 모두 다리에 올라탈 때까지 진행 
    while(!q.empty())
    {
        //@나갈 트럭이 있는가?
        if(!dq.empty())
        {
            //@다리에 첫 번째 올라온 트럭
            int firstTime = dq.front().first;
            int truck = dq.front().second;

            if((time - firstTime) >= bridge_length)
            {
                //@다리 총 무게 감소
                curWeight -= truck_weights[truck];
                //@다리에서 첫 번째 올라탄 트럭 나감
                dq.pop_front();    
            }
        }
        //@탈 트럭이 있는가?
        if(!q.empty())
        {
            //@첫 번째 순서의 트럭
            int truck = q.front();

            if(dq.size() < bridge_length
            && (curWeight + truck_weights[truck] <= weight))
            {
                //@다리 총 무게 증가
                curWeight += truck_weights[truck];
                //@다리에 트럭 올라감
                dq.push_back({time, truck});
                //@트럭 순서 제거
                q.pop();
            }
        }
        //@시간 증가
        time++;
    }
    //@다리 마지막에 올라간 트럭이 내릴때까지 걸리는 시간 더해준다.
    if(!dq.empty())
    {
        time += (bridge_length - (time - dq.back().first));
    }

    return time;
}

 

---