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

https://programmers.co.kr/learn/courses/30/lessons/42583

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

이 문제는 문제 자체를 이해하는데도 굉장히 오래걸렸다. 다리의 길이와 다리에 올라갈 수 있는 트럭의 수를 같은 숫자를 쓰기 때문에도 헷갈렸고 다리를 트럭이 지나는데 다리의 길이만큼 시간이 필요하다는 것도 문제에 적혀져 있지 않아서 너무 아쉬운 문제였다. 이 문제는 쉽게 생각해 다리 길이만큼의 큐를 만들고 while문을 돌면서 트럭이 큐에 들어가게 만드는 것이 가장 쉬운 방법이었다. 코드는 다음과 같다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int on_weight = 0;
    int i = 0;
    queue<int> q; //다리를 나타낼 큐
    for(int i = 0; i < bridge_length; i++) { //다리의 길이만큼 큐에 0을 채움
        q.push(0);
    }
    while(i < truck_weights.size()) { //다리에 트럭이 모두 올라갈 때까지
        if(q.front() != 0) { //다리를 빠져나가는 트럭의 무게를 뺌
            on_weight -= q.front();
        }
        q.pop(); //다리에서 트럭 pop
        answer++; //시간 경과
        if(on_weight + truck_weights[i] <= weight) { //다리에 다음 트럭을 올려도 무게가 넘지 않을 경우
            on_weight += truck_weights[i]; //무게 추가
            q.push(truck_weights[i]); //트럭 다리에 추가
            i++; //다음 트럭
        }
        else { //그렇지 않으면 트럭 추가하지 않고 0 추가
            q.push(0);
        }
    }
    return answer+bridge_length; //마지막 트럭이 다리를 지나는 시간인 다리 길이를 더하여 리턴
}

위의 코드를 보면 다리에 다음 트럭을 올리고자할 때 무게를 넘지 않는지 체크한다. 만약 무게가 넘어갈 경우 트럭을 올리지 않고 다리의 길이를 유지할 0을 큐에 push한다. 마지막에 리턴하기 전에 bridge_length를 더하는 이유는 마지막 트럭이 다리를 모두 지나는데 bridge_length 시간만큼 들기 때문에 더해야한다.

 

큐를 이용해 다리에서 트럭들이 while문을 돌면서 앞으로 하나씩 이동하는 것을 표현하는 것이 핵심이었고 while문을 돌 때마다 시간이 경과하여 시간초과가 날 것이라고 생각했는데 다행히 효용성을 테스트하는 케이스는 없어서 통과할 수 있었다. 실제 구현은 간단했지만 문제 난이도는 3단계로 느껴질정도로 문제를 이해하는 것도 어려웠다. 효용성 테스트가 없어서 2단계 문제인 것 같다.