[프로그래머스] 택배 배달과 수거하기 c++ (2023 KAKAO BLIND RECRUITMENT)

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/150369?language=cpp 

프로그래머스

---

풀이

결국 가장 먼 집부터 들려야 하므로, 그리디 알고리즘으로 해결해야 된다는 것은 알았다.

그러나 for문을 끝부터 돌리기에는 번거로워서 고민하다 stack을 사용하는 방법으로 해결하였다.

스택 관리

deliveries, pickups 별로 스택을 선언한다.

 

여기서 중요한 점은, 가장 먼 집이 택배나 회수할 것이 아무것도 없으면 안된다는 것이다.

왜냐하면, 추후 while문에서 answer에 왕복 거리(stack size * 2)를 더하는데 아무것도 없으면 최소 이동거리가 아니기 때문이다.

// 가장 먼 집이 택배나 회수할게 없으면 안됨
while(!go.empty() && !go.top())
    go.pop();
while(!back.empty() && !back.top())
    back.pop();

 

메인 로직의 while문 내에는 왕복 거리를 더한 뒤, 각 스택별로 계산을 하면 된다.

while(!go.empty() && box <= cap){
	// 택배 실을 수 있을때
    if(go.top() + box <= cap)
        box += go.top();
    // 택배를 다 실을수 없을때
    else{
        go.top() -= (cap - box);
        break;
    }
    go.pop();
}

---

코드

#include <string>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    int box = 0;
    stack<int> go, back;
    
    for(auto elem : deliveries)
        go.push(elem);
    
    for(auto elem : pickups)
        back.push(elem);
    
    // 가장 먼 집이 택배나 회수할게 없으면 안됨
    while(!go.empty() && !go.top())
        go.pop();
    while(!back.empty() && !back.top())
        back.pop();
    

    while(!(go.empty() && back.empty())){
        answer += max(go.size() * 2, back.size() * 2);
        
        box = 0;
        while(!go.empty() && box <= cap){
            if(go.top() + box <= cap)
                box += go.top();
            else{
                go.top() -= (cap - box);
                break;
            }
            go.pop();
        }
        box = 0;        
        while(!back.empty() && box <= cap){
            if(back.top() + box <= cap)
                box += back.top();
            else{
                back.top() -= (cap - box);
                break;
            }
            back.pop();
        }        
    }        
    return answer;
}