프로그래머스_코딩테스트 연습_스택/큐_다리를 지나는 트럭

문제 이름 : 다리를 지나는 트럭

문제 유형 : 스택/큐

작성 언어 : C++

 

 

• 다리를 지나는 트럭

문제 설명

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

예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.

경과 시간                 다리를 지난 트럭                         다리를 건너는 트럭      대기 트럭

0	[]	[]	[7,4,5,6]
1~2	[]	[7]	[4,5,6]
3	[7]	[4]	[5,6]
4	[7]	[4,5]	[6]
5	[7,4]	[5]	[6]
6~7	[7,4,5]	[6]	[]
8	[7,4,5,6]	[]	[]

따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.

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

제한 조건

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

입출력 예

bridge_length  weight         truck_weights                                                                              return

2	10	[7,4,5,6]	8
100	100	[10]	101
100	100	[10,10,10,10,10,10,10,10,10,10]	110

 

 

풀이 :

다리위에 트럭을 올린다면 먼저들어오는 트럭이 먼저나갈것이니 선입선출 자료구조인 Queue를 이용한다

그래서 큐에 트럭을 추가 , 삭제 해가면서 관리해주고,

트럭이 다리를 언제 건너기 시작해서 언제 모두 건넜는지 체크하려면

다리에 진입한 해당시각을 알아야한다 (다리위에서 이동하고 있는거리)

그래서 진입한 시각을 저장하는 Vector 를 선언해준다.

다리위의 하중도 추가,삭제 시점마다 계산해주면 끝

 

+ 문제에서는 모든 트럭의 속도가 1이지만

만약 트럭의속도가 각각 다른 문제가 나온다면 정말 복잡해질것같다.

 

 

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    queue<int> truck_queue;                 //다리위의 트럭
    vector<int> time;                       //트럭들이 다리에 언제진입했는지? 진입시간
    
    int answer = 0;
    int weight_sum = 0;                     //현재다리의 하중
    int tr_count = truck_weights.size();    //입력벡터 크기저장 (반복문 끝나는시점계산용)
    int count = 0;                          //몇대가 지나갔는지
    
    while(1)
    {
        answer++; //1초씩 증가
        
        if(count==tr_count) break; //트럭이 모두나가면 종료 (현재까지나간트럭 == 입력벡터의크기)
        
        if(!truck_weights.empty()) //대기중인 트럭들이 있을때
            if(weight_sum + truck_weights[0] <= weight) // 맨앞의 트럭이 다리에 올라갈수있는지 하중계산
            {
                truck_queue.push(truck_weights[0]);         //다리에 올려주고 (queue)
                weight_sum += truck_weights[0];             //현재 다리하중더해주고
                time.push_back(0);                          //진입시간 계산  (vec)
                truck_weights.erase(truck_weights.begin()); //다리에 올려줬기때문에 입력벡터는 맨앞의 하나 지워준다.
            }
        for(int i=0;i<time.size();i++) //다리위에있는 트럭들 시간 더해주기 (한칸씩앞으로)
        {
            time[i]++;
        }
        
        if(!time.empty())
            if(time[0]==bridge_length) //다리위의 맨앞트럭이 끝에 도달
            {
                weight_sum -= truck_queue.front();  //현재 다리의 하중 감소
                truck_queue.pop();                  //트럭 없애주기
                time.erase(time.begin());           //진입했던시간도 없애주기
                count++;                            //트럭 나간 갯수 세기
            }
    }
    
    return answer;
}

 

 

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

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