문제 42583. 다리를 지나는 트럭

문제 링크

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

프로그래머스

 

난이도 : Lv.2

 

문제 요약 설명

트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.

solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.

입력

• 다리에 올라갈 수 있는 트럭 수 bridge_length
• 다리가 견딜 수 있는 무게 weight
• 트럭 별 무게 truck_weights

입력 제한

• bridge_length는 1 이상 10,000 이하입니다.
• weight는 1 이상 10,000 이하입니다.
• truck_weights의 길이는 1 이상 10,000 이하입니다.
• 모든 트럭의 무게는 1 이상 weight 이하입니다.

입력 예제

// input
2 10 [7,4,5,6] // bridge_length, weight, truck_weights

// ans
8

 

풀이 방식

전형적인 큐(queue) 자료구조를 활용하는 문제이다. 모든 트럭이 다리를 건너되, 다리가 견딜 수 있는 무게만큼만 다리 위에 트럭이 있어야하기 때문에 매 초마다 다음 트럭의 무게를 다리가 견딜 수 있는 지 확인해야한다. 따라서 다음과 같이 로직을 작성한다.

1. 우선 걸린 시간을 1초 증가시킨다.
2. 다리 끝에 트럭이 있다면 해당 트럭의 무게만큼 현재 다리 위에 올라간 트럭들의 무게(이하 cur_w)에서 뺀다.
3. cur_w + 다음 트럭의 무게(truck_wrights[idx])를 다리가 견딜 수 있는 무게인 지 확인한다. 만약 견딜 수 있다면, 해당 트럭의 무게를 push하고, 그렇지 않다면 0을 push한다.

위 과정을 다리에 트럭이 더이상 없을 때까지 반복한 다음 걸린 시간을 리턴하면 정답이 된다.

 

추가) 아래 정답 코드에서는 2번과 3번과정을 반대로 해서 짰는데, 다음 트럭을 다리에 올릴 수 있는 지 확인하고 다리 끝 트럭을 빼거나, 다리 끝 트럭을 뺀 다음 다음 트럭을 다리에 올릴 수 있는 지 확인하거나의 차이라서 로직상 큰 차이는 없다.

정답 코드 

#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 cur_time = 0;
    int cur_w = 0;
    queue<int> q;
    
    for(int truck_w : truck_weights){
        
        // 맨 처음 시작시 트럭을 push한다.
        if(q.empty()){
            q.push(truck_w);
            cur_w += truck_w;
            
            cur_time++;
            cout << cur_w << '\n';
            
            continue;
        } 
        
        bool find = false;
        
        while(!find){
            cur_time++;
            
            // q에 들어가 있는 원소의 개수가 다리의 길이보다 작을 때.
            if(q.size() < bridge_length){
                
                if(cur_w + truck_w > weight){
                    q.push(0);
                }
                else{
                    q.push(truck_w);
                    cur_w += truck_w;
                    find = true;
                }
            }
            // q에 들어가 있는 원소의 개수가 다리의 길이와 같을 때.
            else{
                if(cur_w - q.front() + truck_w > weight){
                    q.push(0);
                }
                else{
                    q.push(truck_w);
                    cur_w += truck_w;
                    find = true;
                }
                
                cur_w -= q.front(); q.pop();
            }
        
            
            
        }
              
    }
    
    // 마지막 트럭은 push만 되고 이동하지 않았으니, 마지막 트럭이 다리를 지나는 시간(bridge_length)을 추가한다.
    answer = cur_time + bridge_length;
    
    return answer;
}