[LeetCode] 2391. Minimum Amount of Time to Collect Garbage

https://leetcode.com/problems/minimum-amount-of-time-to-collect-garbage/description/

Minimum Amount of Time to Collect Garbage - LeetCode

leetcode - Minimum Amount of Time to Collect Garbage

문제 유형 : 구현, 배열, 그리디(?), 문자열처리

문제 난이도 : Medium

 

문제

You are given a 0-indexed array of strings garbage where garbage[i] represents the assortment of garbage at the ith house. garbage[i] consists only of the characters 'M', 'P' and 'G' representing one unit of metal, paper and glass garbage respectively. Picking up one unit of any type of garbage takes 1 minute.

You are also given a 0-indexed integer array travel where travel[i] is the number of minutes needed to go from house i to house i + 1.

There are three garbage trucks in the city, each responsible for picking up one type of garbage. Each garbage truck starts at house 0 and must visit each house in order; however, they do not need to visit every house.

Only one garbage truck may be used at any given moment. While one truck is driving or picking up garbage, the other two trucks cannot do anything.

Return the minimum number of minutes needed to pick up all the garbage.

 

당신은 0-indexed의 문자열 배열 garbage를 받는다.

garbage[i]는 i번째 집의 쓰레기 정보를 문자열 형태로 가지고 있다.

'M', 'P', 'G'로가지고 있고, 각각 metal, paper, glass를 뜻한다.

쓰레기를 처리하는데 1분이 걸린다.

0-indexed의 정수 배열 travel도 받는다.

travel[i]는 i에서 i+1집으로 가기 위한 시간이 담겨있다.

 

도시에는 3가지의 쓰레기차가 있고, 한 쓰레기차만 이동 가능하고, 각 쓰레기차는 한 종류만 수거 할 수 있다.

모든 쓰레기를 치우기까지 걸리는 시간을 반환하시오.

 

 

풀이

모든 쓰레기를 치우기만 하는데 걸리는 시간은 모든 문자들을 합한 값이다.

이동시간은 각 종류별로의 마지막 인덱스만 알아두면, 트럭의 종류별로 마지막 인덱스까지만 누적시키면 된다.

 

코드

C++

class Solution {
public:
    int garbageCollection(vector<string>& garbage, vector<int>& travel) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        
        const int n = garbage.size();
        unordered_map<char, int> lastidx;
        int time = 0;

		// 쓰레기개수 세기 및 각 쓰레기별로 마지막 인덱스 구하기
        for(int i = 0; i < n; i++) {
            for(const auto & gb: garbage[i]) {
                time++;
                lastidx[gb] = i;
            }
        }
        
        // 각 쓰레기차별로 이동하는시간 누적
        for(const auto & move: lastidx) {
            for(int i = 0; i < move.second; i++) {
            	
                time += travel[i];
            }
        }

        return time;
    }
};