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

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

프로그래머스

<풀이>

1. 배달해야할 박스 갯수와 수거해야할 박스 갯수 정보를 입력받는다.

2. 모든 배달과 수거를 마치고 물류창고로 돌아오는 최소거리를 반환한다.

 

<해법>

1. 알고리즘 선택하기

=> 가장 끝에서 부터 가능한 배달과 수거를 최대로 하면 정답을 구할 수 있습니다. 따라서, 저는 그리디 알고리즘을 선택했습니다.

 

2. 자료구조 선택하기

=> 가장 끝에서 부터 배달과 수거를 진행합니다. 그리고 배달과 수거가 완료된 집은 넘어갑니다. 따라서, 저는 후입선출 자료구조인 스택을 선택했습니다.

 

3. 구현 전 정리

=> 아래는 구현 전 정리한 생각입니다.

(1) 끝 집에서 부터 배달과 수거를 진행한다. 이동한 거리는 max(배달해야할 끝집, 수거해야할 끝집) x 2 이다.

(2) 배달해야하는 집, 수거해야하는 집을 스택으로 관리한다. 

자세한 구현은 아래 코드를 참고해주세요.

 

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <algorithm>
 
using namespace std;
 
struct house {
    int idx, boxCnt;
};
 
stack<house> del, pic;
 
long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
 
    for (int i = 0; i < deliveries.size(); i++) {
        int boxCnt = deliveries[i];
        if (boxCnt) {
            del.push({ i + 1, boxCnt });
        }
    }
    for (int i = 0; i < pickups.size(); i++) {
        int boxCnt = pickups[i];
        if (boxCnt) {
            pic.push({ i + 1, boxCnt });
        }
    }
 
    while (true) {
        if (del.empty() && pic.empty()) break;
 
        int delIdx = del.empty() ? 0 : del.top().idx;
        int picIdx = pic.empty() ? 0 : pic.top().idx;
        answer += static_cast<long long>(max(delIdx, picIdx)) * 2;
 
        int delBoxCnt = 0;
        while (!del.empty()) {
            house& h = del.top();
            if (delBoxCnt + h.boxCnt <= cap) {
                delBoxCnt += h.boxCnt;
                del.pop();
            }
            else {
                h.boxCnt -= (cap - delBoxCnt);
                break;
            }
        }
 
        int picBoxCnt = 0;
        while (!pic.empty()) {
            house& h = pic.top();
            if (picBoxCnt + h.boxCnt <= cap) {
                picBoxCnt += h.boxCnt;
                pic.pop();
            }
            else {
                h.boxCnt -= (cap - picBoxCnt);
                break;
            }
        }
    }
 
    return answer;
}

 

그리디 알고리즘에 대해 알아볼 수 있는 문제였습니다.