코딩테스트 -- 택배 배달과 수거하기 - (프로그래머스 / C++)

프로그래머스

문제!

---

당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)
트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

---

요약하면 물류창고에서 각각의 집에 물건을 배달 픽업을 할때 최소거리를 구하는 문제였습니다.

 

생각보다 어려운 문제였습니다... 이게 2단계....?

 

 

단순 que로 구현할 문제인줄 알았는데 집을 만날때마다 계속 해서 탐색하기에는 집의 수가 100000... 

 

그래서 일단 제일끝집, deliveries / pickups 배열에서 0이아닌 가장 끝집을 찾아주었습니다. 

 >>> 무조건 가야하므로! 1번의 운행중에 무조건 들리는 집으로 설정하여 생각해주었습니다.

 

 

 

그러기위해 끝점을 찾는 함수를 만들어 주었고 각 탐색의 양을 줄이기위해 전 끝점을 불러와 거기부터 탐색해주었습니다.

int find(vector<int>&list,int last){ //끝지점
    for(int i=last;i>=0;i--){
        if(list[i]!=0){
            return i;
        }
    }
    return -1;
}

 

끝점을 초기화 해주고 

int temp_del=pickups.size()-1;
int temp_pick=pickups.size()-1;

 

 

이제 탐색을 위한 while문을 돌려줍시다.

 while(1){
        temp_del=find(deliveries,temp_del);
        temp_pick=find(pickups,temp_pick);
        if(temp_del==-1 and temp_pick==-1){
            break;
        }
        
        answer+=max(temp_del+1,temp_pick+1)*2;

끝점을 찾지못한다 >> 더이상 배송/ 픽업이 없다! >> -1

양쪽다 -1일때 멈춰주고 

answer+= 이동거리 *2 해주었습니다.

 

 

그리고 배송과 픽업을 아래처럼 따로 구해주었습니다. (방식은 똑같...)

int sum_del=0;
        int sum_pick=0;
        
        for(int i=temp_del;i>=0;i--){
            if(cap>=sum_del+deliveries[i]){
                sum_del+=deliveries[i];
            }
            else{
                deliveries[i]-=cap-sum_del;
                break;
            }
            deliveries[i]=0;
        }
        
        for(int i=temp_pick;i>=0;i--){
            if(cap>=sum_pick+pickups[i]){
                sum_pick+=pickups[i];
            }
            else{
                pickups[i]-=cap-sum_pick;
                break;
            }
            pickups[i]=0;
        }

운행을 끝점까지 갈때는 배송을 하고 , 돌아올때는 픽업을 한다고 생각하고 짜면 위처럼 편하게 나옵니다...

(이걸 몰라서 해멨습니다.... )

 

 

 

먼가.... 어려웠네요...

더 분발하겠습니다.

 

ALL

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

int find(vector<int>&list,int last){ //끝지점
    for(int i=last;i>=0;i--){
        if(list[i]!=0){
            return i;
        }
    }
    return -1;
}

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    
    
    // min(cap,총합) 만큼 채우고 출발?
    // ? 5 4 3 2 1 순서로 빼고/ 담기  >> 끝부분 체크 계속 줄여나가기
    
    //양쪽중 제일끝에있는걸 가야함...
    
    int temp_del=pickups.size()-1;
    int temp_pick=pickups.size()-1;
    
    while(1){
        temp_del=find(deliveries,temp_del);
        temp_pick=find(pickups,temp_pick);
        if(temp_del==-1 and temp_pick==-1){
            break;
        }
        
        answer+=max(temp_del+1,temp_pick+1)*2;
        
        int sum_del=0;
        int sum_pick=0;
        
        for(int i=temp_del;i>=0;i--){
            if(cap>=sum_del+deliveries[i]){
                sum_del+=deliveries[i];
            }
            else{
                deliveries[i]-=cap-sum_del;
                break;
            }
            deliveries[i]=0;
        }
        
        for(int i=temp_pick;i>=0;i--){
            if(cap>=sum_pick+pickups[i]){
                sum_pick+=pickups[i];
            }
            else{
                pickups[i]-=cap-sum_pick;
                break;
            }
            pickups[i]=0;
        }
    }
    
    return answer;
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!