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

문제 링크

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

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

모든 트럭이 다리를 건너기 위해서 몇 초가 걸리는 지 리턴하는 문제.

풀이

• 풀이 알고리즘

다리위의 트럭은 1초에 1칸씩 움직인다. 그렇기 때문에 다리에 올라간 트럭이 다리를 건너기 위해서는 bridge_length 만큼의 시간이 필요하다.

우리는 모든 트럭이 건너기까지 몇 초가 걸릴지 모르므로 모든 트럭이 건너갈 때까지 반복문을 수행한다.

이때 반복문 1회당 1초가 흘러간다고 생각한다.

먼저 주어진 정보들 외에 추가로 필요한 정보들을 정리해보자.

 

1. 현재 다리위에 있는 트럭들에 대한 정보

다리위에 있는 트럭들의 진행한 거리, 트럭의 무게를 알아야한다.

그래야 해당 트럭이 다리를 건너갔는지, 현재 다리위에 있는 트럭들의 무게의 합은 얼마인지 알 수 있다.

그래서 이 정보들을 저장할 vector<pair<int,int>> on_the_bridge 벡터를 만들어줬다.

 

2. 현재까지 건너간 트럭은 몇 대인가

현재까지 건너간 트럭이 몇 대인지 알아야 반복문을 종료할 수 있다.

건너간 트럭의 총합 == 전체 트럭의 수가 될 때 반복문을 종료한다.

 

3. 현재 다리위에 있는 트럭들의 무게의 총합

현재 다리위에 있는 트럭들의 무게 총합을 알아야 새로운 트럭이 올라갈 수 있는지 파악할 수 있다.

새로운 트럭이 올라가면 해당 트럭의 무게만큼 + 해주고, 트럭이 다리를 건너면 해당 트럭의 무게를 - 해준다.

 

대략 이 정도로 생각할 수 있다.

다음은 반복문 1회( 1초 ) 동안 처리해줘야할 업무들이다.

1. 모든 트럭 1칸씩 이동

on_the_bridge에 있는 모든 트럭들의 진행 거리를 + 1 해준다.

 

2. 건너간 트럭이 있는지 확인

다리는 일방통행이므로 1초에 여러대의 트럭이 한 번에 건널 수는 없다. 그래서 맨 앞에있는 트럭이 건넜는지만 체크하면 된다.

on_the_bridge[0] 트럭의 진행 거리가 다리의 길이보다 길면 통과한 것이다.

통과했다면 다리위의 트럭 무게 합에서 0번째 트럭의 무게를 빼준다.

 

3. 새로운 트럭 입장

새로운 트럭이 입장할 수 있는 조건은 2가지가 있다.

새로운 트럭이 들어가도 다리위 트럭무게의 총합이 다리가 버티는 무게보다 작거나 같아야하고,

현재 다리위에 있는 트럭의 수가 다리의 길이(트럭 수용량)보다 작아야한다.

그래야 새로운 트럭이 들어가도 수용량을 넘어서지 않는다.

이 2가지 조건을 만족하면 새로운 트럭 한 대를 다리에 진입시킨다.

이때, 현재 건너지않고 남아있는 트럭이 없다면 이 과정은 생략한다.

 

• 코드 작성

#include <string>
#include <vector>
#include <deque>
#include <queue>
 
using namespace std;
deque<pair<int,int>> on_the_bridge;
queue<int> truck;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int total_weight = 0;
    int finished = 0; //건너간 차량의 수
    
    for(int i = 0; i<truck_weights.size(); i++)
        truck.push(truck_weights[i]);
    
    while(finished < truck_weights.size()){
        answer++;     
        for(int i = 0; i < on_the_bridge.size(); i++) //다리 위 트럭 한 칸씩 이동
            on_the_bridge[i].first++;
        
        if(on_the_bridge[0].first > bridge_length){ //건너감
            total_weight -= on_the_bridge[0].second;
            finished++;
            on_the_bridge.pop_front(); //건너간 차 처리
        }
        if(truck.empty())
            continue;
        if(bridge_length > on_the_bridge.size()){
            int new_car = truck.front();
            if(total_weight + new_car <= weight){ //새로 한 대 올라갈 수 있으면
                on_the_bridge.push_back({1,new_car});
                truck.pop();
                total_weight += new_car;
            }  
        }
    }
    return answer;
}

이것도 사실 큐를 굳이 이용하지 않아도 되는 문제지만 문제 분류가 스택/큐 문제라서 큐를 이용했다.