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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

생각보다 시간이 좀 걸렸던 문제이다. 확실히 stack, queue 관련 문제를 많이 안풀어봐서 풀이가 잘 생각나지 않는 것 같다.

풀이

queue를 이용하여 1초마다 값을 push하여 다리를 구현하였다. 이렇게 구현하면 q.size()가 bridge_length와 같은 경우 queue의 맨 앞 트럭이 다리를 건넜다는 의미가 되므로 pop해주면 된다. 다리에 올라간 트럭들의 무게가 weight보다 작지만 새로운 트럭이 올라갈 수는 없는 경우에는 0을 push하여 해결하였다.

다리의 길이가 2, 다리가 견딜 수 있는 무게가 10, 트럭별 무게가 [7, 4, 5, 6]인 경우를 예시로 살펴보자.

초기 상태
Queue : [] 

time : 0 

current_weight : 0

 

첫번째 트럭의 무게인 7을 push
Queue : [7] 

time : 1 

current_weight : 7

 

7+4 > 10 이므로 두번째 트럭은 진입하지 못하고 대신에 0을 push
Queue : [7,0]

time : 2 

current_weight : 7

 

queue.size()가 bridge_length와 같으므로 pop해주고 두번째 트럭을 push
Queue : [0,4]

time : 3

current_weight : 4

 

queue.size()가 bridge_length와 같으므로 pop해주고 세번째 트럭을 push
Queue : [4,5] 

time : 4 

current_weight : 7

 

queue.size()가 bridge_length와 같으므로 pop해준다. 5+6 > 10 이므로 네번째 트럭은 진입하지 못하고 대신에 0을 push
Queue : [5,0]

time : 5 

current_weight : 5

 

queue.size()가 bridge_length와 같으므로 pop해주고 마지막 트럭을 push
Queue : [0,6] 

time : 6 

current_weight : 6

마지막 트럭이 다리 길이만큼 시간이 지나면 모든 트럭이 다리를 건넌 것이다.
따라서 마지막 트럭이 진입한 시간인 6초에 다리의 길이인 2를 더하여 8이 정답이다.

코드

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

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int time = 0;
    int cur_weight = 0;
    int idx = 0;
    queue<int> q;
    while (true) {
        time++;
        if (q.size() == bridge_length) {
            cur_weight -= q.front();
            q.pop();
        }

        if (cur_weight + truck_weights[idx] <= weight) {
            if (idx == truck_weights.size() - 1) {
                time += bridge_length;
                break;
            }
            q.push(truck_weights[idx]);
            cur_weight += truck_weights[idx];
            idx++;
        }
        else q.push(0);
    }
    return time;
}