Programers : 다리를 지나는 트럭(queue)

김정욱·2021년 1월 26일
0

Algorithm - 문제

목록 보기
65/249

다리를 지나는 트럭

코드

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

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0, free_weight=weight;
    queue<int> q;
    queue<int> wait;
    for(auto a : truck_weights) wait.push(a);

    while(true)
    {
        /* 종료 하기 위한 조건 --> wait중인 트럭이 없을 때 다리 길이만큼 더하고 종료 */
        if(wait.empty() && !q.empty()){
          answer+=bridge_length;
            break;
        } 
        answer++;
        /* 1) queue가 가득찼을 때마다 pop! */
        if(q.size() == bridge_length){
            free_weight += q.front();
            q.pop();
        }
        /* 2-1) 여유 무게가 있어서 q에 추가 */
        if(q.size() < bridge_length && free_weight >= wait.front()){
            q.push(wait.front());
            free_weight -= wait.front();
            wait.pop();
        /* 2-2) 여유무게는 없으니 0을 q에 추가 */
        }else{
            q.push(0);
        }
    }
    return answer;
}
  • key point!
    1) queue가 가득찼을 때 pop()push()가 하나의 cycle에 존재해야 한다.
    2) pop() 다음에 push()를 해주는 순서가 중요!
    3) queue의 size()로 pop여부를 확인하기 때문에 빈 값(0)을 넣어주어야 한다!
    4) 마지막 모든 트럭이 queue에 올라갔을 때 bridge_length만큼 더하고 break!
profile
Developer & PhotoGrapher

0개의 댓글