뚝딱뚝딱

문제에서 예시로 주어진 접근 순서를 보고, 가장 멀리 있는 집부터 접근해야 한다는 건 다 캐치했을 것이다.

그런데 cap만큼 감소시키는 것을 불규칙한 vector 값에 바로 접근해서 푸는 건 복잡할 것 같았다.

집의 번수 = 물류창고로부터의 거리이고, 거리에 대한 정보도, 각 거리에 있는 집에 두어야 할/ 수거해야 할 택배 개수에 대한 정보도 동시에 가질 수 있는 방법이 무엇이 있을까 생각하다 보니.. 스택이 생각났다.

내가 접근한 방법은 delieveries와 pickups에서 0이 아닌 값을 갖는 인덱스+1(거리는 1부터니까)를 각 택배 개수만큼 스택에 차례로 넣는것이다. 그럼 스택은 뒤에서부터 빼니까, 우리가 원하는 대로 가장 멀리있는 집의 택배를 이용할 수 있게 된다.

두 스택에서 cap만큼씩 삭제하고, 이때 각각의 스택에서 맨 처음 삭제한 값이 가장 멀리까지 가는 거리가 되므로, top1과 top2에 저장해 둔다. 이때 주의할 점은 스택이 비어있지 않은 경우에만 삭제 해야 한다는 점이다.

한번 순회하고 갔다올 때 top1과 top2 중 더 큰 값에 따라서 갔다와야 한번에 해결할 수 있기 때문에 더 큰 값의 2배 만큼을 answer에 더해주면 된다!

c++ 코드는 아래와 같다.

#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> st1, st2;

	for (int i = 0; i < n; i++) {//스택에 다 넣어준다
		for (int j = 0; j < deliveries[i]; j++) {
			st1.push(i + 1);
		}
		for (int k = 0; k < pickups[i]; k++) {
			st2.push(i + 1);
		}
	}

	int top1, top2;

	while (!st1.empty() || !st2.empty()) {//둘다 스택이 비워지면 그만
		top1 = top2 = 0;
        for (int i = 0; i < cap; i++) {
			if (!st1.empty()) {
				if (i == 0) {
					top1 = st1.top();
				}
				st1.pop();
			}

			if (!st2.empty()) {
				if (i == 0) {
					top2 = st2.top();
				}
				st2.pop();
			}
		}
		answer += max(top1, top2) * 2;
		
	}
	
	return answer;
}