2023 카카오 블라인드 코딩테스트 2번 택배 배달과 수거하기 / C++

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

프로그래머스

2023 카카오 블라인드 코딩테스트 1번 택배 배달과 수거하기 문제

 

아이디어

최소거리를 구하는 과정에서 배달과 수거할때 택배를 한번에 처리할 필요가 없기때문에 가장 멀리있는 집부터 cap만큼 긁어오면 될거라고 판단했고 멀리 있는 집부터 확인하기에 stack 자료구조를 사용 적합 판단

배달 또는 수거 해야하는 집이 하나라도 있다면 해당 집까지 들러야 하기 때문에 최대 크기로 왕복거리를 추가했고, 마지막집이 비어있는 케이스를 체크하는것을 주의

 

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


long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
	long long answer = 0;
	stack<int> deliveriesInfo, pickupsInfo;
	for (int i = 0; i < deliveries.size(); i++) {
		deliveriesInfo.push(deliveries[i]);
		pickupsInfo.push(pickups[i]);
	}
	//최대거리의 택배 상자 존재 여부 체크
	while (!deliveriesInfo.empty()) {
		if (deliveriesInfo.top()) {
			break;
		}
		deliveriesInfo.pop();;
	}

	while (!pickupsInfo.empty()) {
		if (pickupsInfo.top()) {
			break;
		}
		pickupsInfo.pop();
	}

	int package = 0;
	auto max = [](int a, int b)->int {return a > b ? a : b; };
	while (!(deliveriesInfo.empty() && pickupsInfo.empty()))
	{
		//배달, 수거중 최대거리에 있는 집 방문시 왕복거리
		answer += max(deliveriesInfo.size() * 2, pickupsInfo.size() * 2);

		package = 0;
		while (!deliveriesInfo.empty() && package <= cap)
		{
			//최대거리의 집에 모두 배달 가능 케이스
			if (cap - deliveriesInfo.top() - package >= 0) {
				package += deliveriesInfo.top();
				deliveriesInfo.pop();
				continue;
			}
			//최대거리 집에 일부 배달 케이스
			deliveriesInfo.top() -= (cap - package);
			break;
		}

		package = 0;
		while (!pickupsInfo.empty() && package <= cap)
		{
			//최대거리의 집에 모두 수거 가능 케이스
			if (cap - pickupsInfo.top() - package >= 0) {
				package += pickupsInfo.top();
				pickupsInfo.pop();
				continue;
			}
			//최대거리의 집에 일부 수거 가능 케이스
			pickupsInfo.top() -= (cap - package);
			break;
		}
	}
	return answer;
}