프로그래머스 택배 배달과 수거하기 C++

 

풀긴 했는데,, 시간이 너무 오래 걸렸다. 코드도 쪼금 아쉽다.

 

코드 예제를 잘 읽어야 된다는 것을 느꼈다!

 

이 문제는 가장 멀리서부터 순차적으로 처리하면 되는 문제이다.

단 예제 풀이에서는 이를 숨기고자, 최선의 방법으론 진행하지 않았지만, 정답상에서는 전혀 지장없는 방법으로 안내했다.

 

처음에 3개의 택배를 놓고 출발하는데, 그냥 MAX로 채워서 출발하면서 다 놓고 오면 된다.

그리고 돌아올 때에도 마찬가지이다.

 

 

놓고 올 택배와, 수거 할 택배의 거리 중 더 먼 곳까지 결국엔 가야 하므로, 둘 중의 MAX 값으로 거리를 계산하고

왕복이니까 x2를 해준다.

 

그리고 스택을 이용해서, 가장 먼 거리에서부터 택배를 몇 개 놓고 몇 개 가져올지를 카운트하며 계산해주면 된다.

#include <string>
#include <vector>
#include <stack>
#include <iostream>

#define MAX(a, b) ((a>b)?a:b)

using namespace std;

/*
우선순위
먼 집 배달, 먼 집 수거

5집 배달 > 5집 수거 > 4집 배달 > 4집 수거 > 3집 배달 > 3집 수거 ...

예제에는 거리는 같지만, 굳이 문제를 어렵게 만들기 위해
첫 시작 지점에서 집 3에 하나 더 배달할 수 있지만 안 하고 있다.
*/

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    
    stack<pair<int ,int>> stackDeliver;
    stack<pair<int, int>> stackPickup;
    
    for(int i = 0; i < n; i++) {
        
        if(deliveries[i] > 0) {
            stackDeliver.push({i + 1, deliveries[i]});
        }
        if(pickups[i] > 0) {
            stackPickup.push({i + 1, pickups[i]});
        }
    }

    
    // {1, 1}, {3, 2}, {4, 1}, {5, 2};
    // {2, 3}, {4, 4}
    
    while(!(stackDeliver.empty() && stackPickup.empty())) {
                
        int dLen = stackDeliver.empty() ? 0 : stackDeliver.top().first;
        int pLen = stackPickup.empty() ? 0 : stackPickup.top().first;
        
        answer += (MAX(dLen, pLen)) * 2;
        
        
        int counter = 0;
        
        while((!stackDeliver.empty()) && counter++ < cap) {
            if(--stackDeliver.top().second == 0)
                stackDeliver.pop();
        }
        
        counter = 0;
        
        while((!stackPickup.empty()) && counter++ < cap) {
            if(--stackPickup.top().second == 0)
                stackPickup.pop();
        }
    }
        
    return answer;
}

 

 

그리고 어떤 분이 대단한 풀이를 올려주셨다. 아주 친절한 설명과, 짧은 코드였다.

https://school.programmers.co.kr/questions/43364

 

이 풀이를 보고 느낀 것은, 나도 이런 생각을 하고 싶다는 것이다.

정말 풀이의 결이 다르다 라고 느꼈다.

 

그리고 이 생각을 그대로 나도 풀어보았다.

#include <string>
#include <vector>

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    
    
    int d = 0, p = 0, count = 0;
    
    for(int i = n - 1; i >= 0; i--) {
        
        
        d -= deliveries[i];
        p -= pickups[i];
        count = 0;
        
        while(d < 0 || p < 0) {
            
            d += cap;
            p += cap;
            count++;
        }
        
        answer += (i + 1) * 2 * count;
        
        
    }
    
    
    
    return answer;
}