[JS][프로그래머스 -LEVEL 2 - 택배상자수거하기 ]

문제 해설

• 어쩌피 우리가 가야되는 길은 가장 먼곳이다. ( 먼곳부터 하나씩 없애줘야 그나마 작은
  거리가 나온다는 것을 알것이다.
• 배달하는 곳과 vs 수거하는 곳의 길이를 비교해서 긴 거리부터 간다고 가정한다.
• 이때 수거책은 limit 가 존재하기 때문에 이것을 맞춰서 조절해서 -limit 를 해줘야된다.

시간복잡도 통과 못한 코드

function solution(cap, n, deliveries, pickups) {
   var answer=0;
    /*
    if(cap<1 || cap>50) return;
    if(n<1|| n>100000) return;
    if(deliveries.length!= pickups.length || 
      deliveries.length!=n || pickups.length!=n) return
      */
    
    const find_index= function(del,pic,indexx){
  
        for(var i=indexx; i>=0; i--){
            if(del[i]!=0 || pic[i]!=0){
                return i;
            }
            else{
                deliveries.pop();
                pickups.pop();
            }
        }
    }
    
   

    var total_delver= deliveries.reduce((ac,cur)=> ac+cur);
      var total_pic= pickups.reduce((ac,cur)=> ac+cur); 
    
    //console.log(total_delver,total_pic )
     var index=n-1;
    while(total_delver>0 || total_pic>0){
     
     
       var plus_delver=0;
       var plus_pick=0;
 
       var in_index=find_index(deliveries,pickups,index);
       index=in_index;
   
      answer+=  (in_index+1)*2;
       for(var ig=in_index; ig>=0; ig--){
               if(plus_delver>cap && plus_pick>cap){
                   break;
               }
           if(plus_delver<cap){
              plus_delver+=deliveries[ig]; 
              total_delver-=deliveries[ig];
             deliveries[ig]=0; 
               //여기서 더했는데..? 작아졋다면
               if(plus_delver>cap){
                    deliveries[ig]=plus_delver-cap
                   total_delver+=(plus_delver-cap)
               }
        
           }
                if(plus_pick<cap){
                     plus_pick+=pickups[ig]; 
                     total_pic-=pickups[ig];
             pickups[ig]=0; 
               //여기서 더했는데..? 작아졋다면
               if(plus_pick>cap){
                    pickups[ig]=plus_pick-cap
                     total_pic+=(plus_pick-cap)
               }
           }
             
       }
    
    }
  return answer;  
}

완전 탐색으로 수식을 짰더니

아무리 해도 3개 부분은 시간 초가가 났다.

이방법은 아닌듯한다.

해결방안

• 완전 탐색으로 다시 가야되는 거리를 찾는것이 아닌. STACK 를 사용해서 가야되는 거리 를 자동으로 가게하는 식로 하면된다,
  즉 스택을 가까운 거리부터 먼 거리 까지 쌓은후 CAP 만큼빼주면서 가면 될듯하다.
• 스택