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

코딩테스트 연습 - 다리를 지나는 트럭 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

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

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int temp = 0;
    queue<int> que;
    int i = 0;
    while(i < truck_weights.size())
    {
        if(temp + truck_weights[i] <= weight)
        {
            if(que.size() == bridge_length)
            {
                temp -= que.front();
                que.pop();
            }
            que.push(truck_weights[i]);
            temp += truck_weights[i];
            i++;
        }
        else
        {
            if(que.size() < bridge_length)
                que.push(0);
            else
            {
                temp -= que.front();
                que.pop();
                if(temp+truck_weights[i] > weight)
                    que.push(0);
                else
                {
                    que.push(truck_weights[i]);
                    temp += truck_weights[i];
                    i++;
                }
            }
        }
        answer++;
    }
    answer += bridge_length;
    return answer;
}

풀이 방법

선입 선출인 queue를 이용해서 풀었어야 하는 문제였다. 트럭이 지나가는 다리는 선입선출 구조이기 때문이다.

트리를 계속해서 queue에 push하면서 매 시행마다 temp로 queue에 쌓인 값을 갱신하고,

temp가 weight보다 클 경우 queue에 0을 push한다.

queue의 size가 bridge_length가 될 경우 queue에서 pop을 해주며, 그와 동시에 temp도 pop한 값만큼 빼며 갱신한다.

매 실행마다 queue의 총합인 temp가 조건에 만족하는지 보며, push할 수 있을때는 주어진 truck_weights의 인덱스를 증가시켜 새로운 값을 push해주고 아닐 때는 0을 넣어준다.

만약 인덱스가 마지막 값이 됐을 경우엔 마지막 bridge길이만큼 건너면 되므로 마지막으로 더해준다. 끝!

 

queue의 자료구조의 쓰임을 정확히 알고 있으면 풀기 수월했을 문제.