2391. Minimum Amount of Time to Collect Garbage

• 3개의 쓰레기 종류가 있으며 한 번에 한 종류 씩 쓰레기 수거 트럭을 보내서 처리하는데 걸리는 시간의 합을 구하면 된다.

• 한번에 한 종류씩 수거가 가능하므로 각 쓰레기 종류를 수거하는데 걸리는 시간을 독립적으로 계산할 수 있다.

• 다만 쓰레기 수거 트럭이 모든 집을 방문해야 하는 것은 아니므로 이동 시간 travel 의 합은 쓰레기 종류 별로 다를 수 있는데 이는 prefixed sum 을 사용하여 미리 계산해 둘 수 있다.

• 각 쓰레기 수거 트럭이 방문해야 되는 마지막 집의 index를 기억해두었다가 prefixed sum으로 구한 해당 지점까지의 이동 거리 합을 결과에 더하면 된다.

• 쓰레기를 수거하는 시간 자체도 굳이 쓰레기 종류 별로 셀 필요 없이 해당 집의 쓰레기 숫자 garbage[i].length() 를 더하여 한번에 구해도 된다.

• 이 문제를 조금 변형한다면 다음과 같은 방식으로 가능할 것 같다.
• 쓰레기 종류가 3가지가 아닌 N가지인 경우
• 쓰레기 종류 별로 서로 다른 처리 시간이 걸리는 경우
• 동시에 각 쓰레기 종류 별 트럭이 수거할 수 있는 경우
• 동시에 수거 가능하지만 같은 집을 방문하는 경우 나중에 방문한 트럭이 대기해야 하는 경우

enum GarbageType {
    Empty = 0,
    Metal = 1,
    Paper = 2,
    Glass = 4,
};

inline GarbageType operator | (GarbageType lhs, GarbageType rhs) {
    return static_cast<GarbageType>(
        static_cast<int>(lhs) | static_cast<int>(rhs)
    );
}

inline GarbageType operator & (GarbageType lhs, GarbageType rhs) {
    return static_cast<GarbageType>(
        static_cast<int>(lhs) & static_cast<int>(rhs)
    );
}

class Solution {
public:
    GarbageType checkType(string& garbage) {
        GarbageType type = Empty;
        for (auto g : garbage) {
            switch (g) {
                case 'M': type = type | Metal; break;
                case 'P': type = type | Paper; break;
                case 'G': type = type | Glass; break;
            }
        }
        return type;
    }

    int garbageCollection(vector<string>& garbage, vector<int>& travel) {
        int result = garbage[0].length();
        vector<int> lastIndex(3, 0);
        for (int i = 1; i < travel.size(); ++i) {
            travel[i] += travel[i - 1];
        }
        for (int i = 1; i < garbage.size(); ++i) {
            auto type = checkType(garbage[i]);
            result += garbage[i].length();
            if (type & Metal) lastIndex[0] = i;
            if (type & Paper) lastIndex[1] = i;
            if (type & Glass) lastIndex[2] = i;
        }
        for (auto index : lastIndex) {
            if (index > 0) result += travel[index - 1];
        }
        return result;
    }
};