[Programmers - lv02] 다리를 지나는 트럭 (cpp / python)

다리를 지나는 트럭

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

 

문제 설명

다리를 queue라고 생각하고 조건을 적절히 이용하여 푸는 문제다. 어렵지는 않지만 생각해야할 조건이 많아서 좀 까다로웠다.

자세한 풀이는 c++코드에 주석처리 해놓았다.

파이썬 코드도 로직자체는 같지만 for문에서 인덱스값을 마음대로 조절할 수 없어서 while문을 이용하였다.

문제 풀이

소스코드 : C++

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#define PII pair<int, int>
using namespace std;

struct onBridge{int weight, time;}; // 트럭, 진입 시간
int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 1, cur_weight=0, cur_time=0;
    queue<onBridge> q;
    q.push({truck_weights[0], answer}); // 첫 번째 트럭 진입
    cur_weight+=truck_weights[0];
    for(int i=1; i<truck_weights.size(); i++){
        int next = truck_weights[i];    // 대기중 트럭
        answer++;   // 다리 위 트럭들 한 칸씩 움직임
        cur_time = q.front().time;        
        if(answer - cur_time == bridge_length){ //다리 통과 처리
            cur_weight -= q.front().weight;
            q.pop();
        }
        if(cur_weight + next <=weight){ //하중을 버틴다면 다음 트럭 추가
            cur_weight+=next;
            q.push({next, answer});
        }
        else --i;   //하중을 버티지 못하면 다음 트럭 대기
    }
    while(!q.empty()){  // 남은 트럭 처리
        answer++;   // 다리 위 트럭들 한 칸씩 움직임
        cur_time = q.front().time;        
        if(answer - cur_time == bridge_length){ // 다리 통과 처리
            cur_weight -= q.front().weight;
            q.pop();
        }
    }

    return answer;
}

소스코드 : Python

def solution(bridge_length, weight, truck_weights):
    answer=1
    cur_weight, cur_time = truck_weights[0], 0
    q = [[truck_weights[0], answer]]
    i=1
    while i < len(truck_weights):
        nxt = truck_weights[i]
        answer+=1
        cur_time = q[0][1]
        if answer - cur_time == bridge_length:
            cur_weight -= q[0][0]
            q.pop(0)
        if cur_weight + nxt <= weight:
            cur_weight +=nxt
            q.append([nxt, answer])
        else: i-=1
        i+=1

    while len(q):
        answer+=1
        cur_time = q[0][1]
        if answer - cur_time == bridge_length:
            cur_weight -=q[0][0]
            q.pop(0)

    return answer