프로그래머스 level -2 연습-다리를 지나는 트럭

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

프로그래머스

정답:

#include <string>
#include <vector>
#include<iostream>
#include<queue>
using namespace std;
struct customTru{
    int weight;
    int time; 
};
int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int totalWeight=0;
  
    int j=0;
    vector<customTru> bridge;
    vector<int>arrive;
    static int count=truck_weights.size();
  //  queue<int> bridge;
    while( truck_weights.size()>0||bridge.size()>0){
           answer++;
        
         
         //다리위 진행 시간
        for(int k=0;k<bridge.size();k++){
            (bridge.begin()+k)->time=(bridge.begin()+k)->time+1;
           // cout<<"outputTime:";//<<//outputTime<<endl; //각각의 다리위의 트럭의 시간
        }
       
         //길이
        if(!bridge.empty()){  
          if(bridge.begin()->time>bridge_length){ //첫번째 트럭이 다리의 길이를 걷넛을때 
               totalWeight= totalWeight-bridge.begin()->weight; //첫번째 트럭 무게 제거 
              // bridge.pop(); //다리에서 제거 
              arrive.push_back(bridge.begin()->weight);
              bridge.erase(bridge.begin());
              
   
               }
        }
        
        
        //무게
       if(!truck_weights.empty()){
       if(totalWeight+truck_weights[0]<=weight){
           customTru tmp;
           tmp.weight= truck_weights[0]; //현재 트럭 
           tmp.time=1;//들어온트럭 시간
           bridge.push_back(tmp); //다리위
           truck_weights.erase(truck_weights.begin());//truck_weights bridge로 넘어감
           totalWeight=totalWeight+ (bridge.back()).weight;//현재 다리의 총무게 
           
       }
        }
        
     
    }
    
    
    return answer;
}

200819

#include <string>
#include <vector>
#include<iostream>
#include<queue>
using namespace std;
struct BridgeOnTruckWeightLength{
    int weight;
    int length;
};
vector<BridgeOnTruckWeightLength>bridgeOnTruck;
int bridgeNowWeight=0;
int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
 
     
  while(truck_weights.size()>0||bridgeOnTruck.size()>0){
      /*
       cout<<"answer:"<<answer;
          cout<<endl;
      cout<<"truck_weights:";
          for(int i=0;i<truck_weights.size();i++){
              cout<<truck_weights[i]<<",";
          }
          cout<<endl;
          cout<<"bridgeNowWeight:"<<bridgeNowWeight<<",";
          cout<<endl;*/
      //bridgeNowWeight=0;
      
  for(int i=0;i<bridgeOnTruck.size();i++){
            bridgeOnTruck[i].length+=1;//현재 존재하는 트럭들 이동
            
   }
      
    for(int i=0;i<bridgeOnTruck.size();i++){
        if(bridgeOnTruck[i].length>=bridge_length){
                bridgeNowWeight-=bridgeOnTruck[i].weight;
                bridgeOnTruck.erase(bridgeOnTruck.begin()+i);//거리에 도달시 pop
                
            }
    } 
    
    
   
  
    
     //들어올 트럭과 이전 트럭 무게의 다리위 무게 체크
      
    if(bridgeNowWeight+truck_weights[0]<=weight&&truck_weights.size()>0){
        
        
        
        
        BridgeOnTruckWeightLength tmpData;
        tmpData.weight=truck_weights[0];
        tmpData.length=0;
        
           //다리위 에 트럭 무게
         bridgeNowWeight+=truck_weights[0];
        
        bridgeOnTruck.push_back(tmpData);//트럭 다리위로 출발 
        
        truck_weights.erase(truck_weights.begin());//출발햇으니 시작점에서 제거 
   
        
        
    }
         
         
    
      answer++;
   }
   
   
    
    
    //다리를 완전히 지남 
    
    
    
    return answer;
}

지난번엔 상당히 시간많이 잡아먹엇는데 생각보다 쉽게 풀엇다 

 

이부분떄문에

정답이 안되는 코드인데 보면 길이가 도달해서 트럭이 나가면서 bridgeOnTruck 사이즈가 줄어들면서 for문이 최종 2번돌아야는게 1번만 돌고 끝이난다.

for(int i=0;i<bridgeOnTruck.size();i++){
            bridgeOnTruck[i].length+=1;//현재 존재하는 트럭들 이동
              if(bridgeOnTruck[i].length>=bridge_length){
                bridgeNowWeight-=bridgeOnTruck[i].weight;
                bridgeOnTruck.erase(bridgeOnTruck.begin()+i);//거리에 도달시 pop
                
            }
   }
      
   

이를 해결을 위해서 길이를 먼저 더해서 계산해주고 

이제 다리를 지난 트럭들을 뺴주는 식으로 가야한다. 

for(int i=0;i<bridgeOnTruck.size();i++){
            bridgeOnTruck[i].length+=1;//현재 존재하는 트럭들 이동
            
   }
      
    for(int i=0;i<bridgeOnTruck.size();i++){
        if(bridgeOnTruck[i].length>=bridge_length){
                bridgeNowWeight-=bridgeOnTruck[i].weight;
                bridgeOnTruck.erase(bridgeOnTruck.begin()+i);//거리에 도달시 pop
                
            }
    } 
    

201007

이번에 dequpe를 이용해서 풀어보았다

다리위가 즉 들어올땐 push_back 나갈때 pop_front를 이용하였으며 

while문 돌릴때 truch_weights 값이 전부다 빠지면truch_weights[0] 를 사용이 불가하니 이때 꼭 체크를하자 truch_weights.size()>0이상체크를해주자

#include <string>
#include <vector>
#include<iostream>
#include<deque>
using namespace std;
struct truckState{
  int weight;
   int length; 
};


int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int answer = 0;
    int bridgeWeightLimit=weight;
    int bridgeWeightNowState=0;
    int count=0;
    deque<truckState> bridge_state; //다리 현재 상태
    for(int i=0;i<truck_weights.size();i++){
      //  cout<<truck_weights[i];
    }
    
  while(truck_weights.size()>0||bridge_state.size()>0){
     answer++;
    if(truck_weights.size()>0){
    if(bridgeWeightNowState+truck_weights[0]<=bridgeWeightLimit){
         bridgeWeightNowState=bridgeWeightNowState+truck_weights[0];  //들어오는 트럭 
        
         truckState tmpState;
         tmpState.weight=truck_weights[0];
         tmpState.length=1;
      //  cout<<truck_weights[1]<<",";
      //  cout<<truck_weights[0]<<",";
        bridge_state.push_back(tmpState);
        truck_weights.erase(truck_weights.begin());
       //  count++;
    }
 }
      
      
    if(bridge_state.size()>0){
    if(bridge_state[0].length<=bridge_length){
        for(int i=0;i<bridge_state.size();i++){
             
            bridge_state[i].length+=1;
          //  cout<< bridge_state[i].weight<<",";
           //  cout<< bridge_state[i].length<<",";
            
           
        }
      //   cout<<":";
     //  cout<<answer;
      //  cout<<endl;
        
        
    }
        
    if(bridge_state[0].length>bridge_length){
        bridgeWeightNowState-=bridge_state[0].weight;
        bridge_state.pop_front();
       
    }
        
    }
     
    
       
    }
 
 answer++;
    
    return answer;


}