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

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

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

 

문제 접근법

• 먼저 진입한 트럭이 먼저 나가므로 queue를 사용합니다.
• vector에 접근하기 위한 index 및 다리 위에 올라간 트럭들의 무게를 합, 출력할 정답을 나타낼 변수를 선언합니다.
• 다리 위 트럭들의 무게와 다음 트럭의 무게의 합을 다리가 견딜수 있는 무게인지 비교합니다.
  • 가능 할 경우
    • vector 인덱스 값이 truck_weights의 길이 - 1 값이라면 모든 트럭이 다리에 올라온 것이므로, 출력 값에 다리의 길이만큼을 더한 후 출력값을 return 합니다.
    • 다음 트럭무게를 추가하고 그 트럭이 마지막 트럭인지를 확인합니다.
    • 마지막일 경우 다리의 길이만큼 출력 값에 더해줍니다.
    • 마지막이 아닐 경우 queue에 트럭을 추가하고, 다리 위 트럭무게에 더하고, vector 접근 인덱스 값을 증가시킵니다.
  • 불가능 할 경우
    • queue에 있는 트럭들이 앞으로 가야하기 때문에 queue안에 0값을 집어넣어 줍니다.
• q의 크기가 다리의 길이와 같다면 다리가 꽉 찬것이므로 다리 위 트럭무게 합에서 queue의 맨 앞값만큼 뺀 후, queue를 pop합니다.

 

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int sum = 0;
    int count = 0;
    queue<int> q;
    
    while(1)
    {    
        answer++;
        
        if(sum + truck_weights[count] <= weight)
        {
            if(count == truck_weights.size() - 1)
            {
                answer += bridge_length;
                break;
            }
            
            q.push(truck_weights[count]);
            sum += truck_weights[count];
            count++;
        }
        else
        {
            q.push(0);
        }
        
        if(q.size() == bridge_length)
        {
            sum -= q.front();
            q.pop();
        }
    }
    
    return answer;
}