Programmers - 택배 배달과 수거하기

Programmers - 택배 배달과 수거하기

오랜만에 올려보는 알고리즘 문제이다. 앞으로 다시 꾸준히 해야겠다!

처음 문제를 봤을 때 제일 멀리 있는 집에 택배를 가져다주고, 올 때도 멀리 있는 집의 빈 상자를 가져오면 된다고 생각하였다.

따라서 주어진 vector를 뒤에서부터 탐색하며 최대한으로 가지고 올 수 있는 양을 가져오고, 가져온 곳은 0으로 치환하는 방법을 사용하였다.

하지만, vector의 길이는 최대 10만이었고 cap이 1이고 각각의 집이 모두 1개씩 상자가 있으면 O(N^2)이 되어버렸다...

제일 뒤에 있는 집을 계속해서 접근하게 되니까, stack을 사용하면 알맞을 것이라 생각했다!

#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;
    stack<int> go;
    stack<int> back;
    // 값들을 모두 스택에 넣어준다
    for(auto i : deliveries){
        go.push(i);
    }
    for(auto i : pickups){
        back.push(i);
    }
    // stack이 모두 빌때까지 동작
    while(!go.empty() || !back.empty()){
        int temp = 0;
        // 가장 먼 집이 0인 경우는 갈 필요가 없으므로 제거해준다.
        while(!go.empty() && go.top() == 0)
            go.pop();
        while(!back.empty() && back.top() == 0)
            back.pop();
        // 택배를 가져다 주러 가거나, 빈 상자를 가지러 가거나 둘 다 가야하니
        // 둘 중에 더 멀리 있는 곳까지 가야한다!
        answer += max(go.size(), back.size()) * 2;
        // 택배를 실을 수 있는 만큼 실어준다
        while(!go.empty() && temp < cap){
            if(temp + go.top() <= cap){
                temp += go.top();
                go.pop();
            }
            else {
            	// 언제나 딱 떨어지진 않을 것이니 최대한으로 실어준다.
                go.top() -= cap - temp;
                temp = cap;
            }
        }
        temp = 0;
        // 빈 상자를 가져올 수 있는 만큼 가져온다.
        while(!back.empty() && temp < cap){
            if(temp + back.top() <= cap){
                temp += back.top();
                back.pop();
            }
            else {
                back.top() -= cap - temp;
                temp = cap;
            }
        }
    }
    return answer;
}

위의 방법으로 해결하였다.

상자를 실을 때 딱 떨어지지 않는 경우 즉, 한번에 한 집의 택배를 모두 가져다주지 못하거나 한 번에 한 집에 있는 모든 상자를 수거하지 않는 경우를 고려하지 않아서 시간 초과가 났었다..

go.top() -= cap - temp;

이 부분!
당연히 저게 없으면 실을 수 있는 최대 상자 갯수보다 한 집의 택배가 많으면 평생 못가져다 줄 테니 무한 loop를 도는 것이 맞다.

오랜만에 카카오 문제를 보니 다시 열심히 해야겠다는 생각을 하게 되었다!