프로그래머스[programmers] - 택배 배달과 수거하기(C++)[LV2]

문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/150369

프로그래머스

 

 

문제 해석

최소 거리로 모든 배달과 수거를 마쳐야 한다.
항상 모든 배달과 수거는 거리가 먼 집을 우선적으로 해결해야 한다.

 

문제 풀이

• 우선 입력받은 배달배열과, 수거 배열들을 초기화하는 작업을 시켜야 합니다.
  • 초기화작업은 맨끝에서 부터 이루어지며, 값이 0이라면 배열에서 제외시켜 줍니다.
  • 0,1,0이라면 맨 끝에 0만 제거됩니다. 즉 , 한 번이라도 0이 아닌 값을 만난다면 탈출해 줍니다.
• 트럭은 배달하는 지역 vs 수거하는 지역 중에서 더 멀리 가는 지역을 필연적으로 방문해야 합니다.
  • 따라서 함수 호출 시, 배달 배열과 수거 배열의 크기를 비교해서 더 큰 값 *2를 해주면 됩니다.(왕복)
• 배달과 수거는 역순으로 진행합니다.
  • 왜냐하면 우리는 우선적으로 가장 먼 지역부터 배달과, 수거를 완료해야 하기 때문입니다.
  • 두 가지 경우의 수가 있습니다.
    1. 현재 트럭에 (실린/실어야 할) 박스보다 (배달/수거)가 넘치는 경우
       • 위와 같은 경우는 모자란 부분만큼 해당 지역에서 값을 빼주고, 과정을 마무리합니다.
    2. 현재 트럭에 (실린 실어야 할)  박스보다 (배달/수거)가 모자란 경우
       • 위와 같은 경우는 해당 지역의 박수 수만큼 값을 빼주고, 과정을 진행합니다.
• 만약 진행하다가, (배달/수거)해야 할 상자의 양이 0이 된다면, 배열에서 빼줍니다.
• 기본적으로 반복의 종료조건은,
  배달하는 과정에서는 배달하는 상자의 양이 cap값을 넘는 경우
  수거하는 과정에서는 수거하는 상자의 양이 cap값을 넘는 경우입니다.

 

💻전체 코드

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

long long dis = 0;
int lim = 0;
void funct(vector<int> &deliveries, vector<int> &pickups);
long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups)
{
    long long answer = -1;
    lim = cap;
    for (int i = n - 1; i >= 0; i--)
    {
        if (deliveries[i] == 0)
            deliveries.pop_back();
        else
            break;
    }
    for (int i = n - 1; i >= 0; i--)
    {
        if (pickups[i] == 0)
            pickups.pop_back();
        else
            break;
    }
    while (!(deliveries.empty() && pickups.empty()))
    { // 수거, 배달이 모두 0일때 종료함
        funct(deliveries, pickups);
    }
    answer = dis;
    return answer;
}
void funct(vector<int> &deliveries, vector<int> &pickups)
{
    int tempD = 0; // 배달상자.
    int tempP = 0;
    bool check = false;
    dis += max(deliveries.size() * 2, pickups.size() * 2);
    for (int i = deliveries.size() - 1; i >= 0; i--)
    { // 거꾸로 시작.
        if (deliveries[i] == 0 && check == false)
        {
            deliveries.pop_back();
            continue;
        }
        if (tempD == lim) //꽉 채운 경우
        {
            break;
        }
        if (deliveries[i] != 0)
        { // 배달할 상자가 있다면.
            check = true;
            if (lim < tempD + deliveries[i])
            { // 현재 트럭에 있는 상자수보다 더 필요하다면.
                deliveries[i] -= lim - tempD;
                tempD += lim - tempD; //
            }
            else // 현재 트럭에 있는 상자수로 해결된다면
            {
                tempD += deliveries[i];
                deliveries[i] = 0;
            }
            if (deliveries[i] == 0)
            {        
                deliveries.pop_back();
                check = false;
            }
        }
    }
    check = false;
    for (int i = pickups.size() - 1; i >= 0; i--)
    {
        if (check == false && pickups[i] == 0)
        { // 아직 한번도 방문안하고, 0개라면 그냥 빼줌.
            pickups.pop_back();
            continue;
        }
        if (tempP == lim)
        { // 꽉꽉채웟음.
            break;
        }
        if (pickups[i] != 0)
        { // 픽업할 상자가 있다면.
            check = true;
            if (tempP + pickups[i] > lim)
            {
                // 현재 트럭에 있는 상자수 + 수거한 상자수가 크다면. 일단 할 수 있는 만큼 담는다.
                pickups[i] -= (lim - tempP); // 담은 만큼 빼준다.
                tempP = lim; // 최대로 찻음.
            }
            else
            { // 방문한곳에서 전부다 수거 할 수 있으면.
                tempP += pickups[i];
                pickups[i] = 0;
            }
            if (pickups[i] == 0)
            {
                pickups.pop_back(); // 픽업을 했는데 , 만약 맨 위가 아니라면.
                check = false;
            }
        }
    }
}

 

느낀 점

• 테스트 케이스 하나에서 계속 막혀서 굉장히 골치 아팠는데, 배열 초기화 문제였다.
  • 나는 항상 배열 size만큼 거리를 계산했는데, 굳이 방문하지 않아도 될 도시의 거리까지 계산한 것이었다.
  • 그래서 함수 호출 전에 뒤에서부터 배달 상자가 0인 지역을 빼줬다.
• 조금 더 간단한 코드로는 스택을 사용해도 지장 없었을 거 같다. 내 실수!