[프로그래머스 lv 2] 다리를 지나는 트럭 (c++)

문제

---

 

 

풀이

---

 

예제로 봐도 처음에는 문제가 이해가 잘 되지 않았다. 문제에 다리를 지나는 시간은 1초에 1씩 간다는 얘기만 있어도 좋았을 것 같다.  즉 트럭 하나가 bridge_length 가 2인 다리를 지나는 시간은 2초가 걸리는 것이다. 

 

 

 

다른 사람이 작성한 표를 보니, 문제 이해가 단박에 되었다.

 

 

 

 

 

예시를 표로 작성해서 가져온 것이다. 7이 다리에 있는 동안 그 뒤의 4는 들어오지 못할 때, 7만 계속 전진해서 2초 뒤 빠져나가는 것이다. 이걸 보고 문제를 이해할 수 있었다.

 

 

 

 

위의 방식을 그대로 코드로 구현했다. 

 

 

#include <bits/stdc++.h>

using namespace std;

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

 

 

 

1. i는 몇 번째 트럭인 지를 가리키고, sum은 다리 위에 트럭 무게 총합을 나타낸다.

 

2. 반복문을 시작하면, answer가 1 증가한다. 1초가 지남을 의미한다.

 

3. 만약 마지막 트럭이라면, 그 트럭이 다리를 지나가는 시간을 한 번에 answer에 더해준다. 트럭 하나가 다리를 지나가는 시간은 bridge_lengh 이다.

 

4. 만약 다리에 최대 트럭 개수 만큼 올라가 있다면, 맨 앞의 트럭을 pop해서 목적지에 도착했음을 나타낸다. 

 

5. 다리 위에 트럭들 무게를 계산했을 때, 새로 트럭이 들어와도 된다면, 트럭을 올린다. (즉 큐에 push한다.) 이 때, sum도 그 무게 만큼 증가시킨다. 

 

   - 만약 새로 트럭이 들어가면 상한 무게가 넘어갈 때, 트럭을 진입시키지 않는다.(0을 넣는 것은 자리를 밀어내기 위함이다.) 

 

 

 

 

 

0을 piush하는 걸 이용해 트럭이 들어가지 않고 다리 위 트럭은 1만 큼 전진한다는 것을 보여주는 아이디어가 감명깊었다. 어쩌면 큐의 근본적인 접근이지 않을까 라는 생각이 든다.