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

문제 요약

• 알고리즘 분류: 누적합, 문자열
• 난이도: Medium
• 문제내용:
  • garbage 배열: 각 집의 쓰레기 종류 ('M', 'P', 'G')를 나타냄.
  • travel 배열: 집 간 이동 시간 제공.
  • 각 트럭은 특정 쓰레기  ('M', 'P', 'G') 유형만 수거함.
  • 트럭은 집 0번에서 시작하며 필요한 집만 방문 가능.
  • 모든 쓰레기를 수거하는 데 필요한 최소 시간을 계산하여
• 사이트 주소: https://leetcode.com/problems/minimum-amount-of-time-to-collect-garbage/description/

 

문제풀이

 이번 문제는 O(N)만큼 요구하는 문제이다. 그래서 누적합으로 풀어야한다. 누접합 관련 내용은 아래글에서 확인 해보면 된다.

https://jih3508.tistory.com/50

[알고리즘 이론] 구간합, 누적합(prefix sum)

문제 접근 방법

 이번 문제에는 어떻게 누적합으로 접근할것인데... 의외로 간단하다.

 먼저, 각 쓰레기 유형('M', 'P', 'G')의 총 쓰레기 개수를 계산하면서, 해당 쓰레기가 마지막으로 발생한 인덱스 위치를 기록한다.

 그다음, 집 간 이동 시간을 누적 계산한 뒤, 각 쓰레기 유형의 마지막 위치에서 해당 누적 이동 시간을 더해주면 된다. 이를 통해 각 쓰레기 유형을 수거하는 데 걸리는 시간을 효율적으로 구할 수 있다. 코드는 아래 글 확인 해보면 된다.

마무리

정리 하자면 아래와 같다.

1. 각 garbage 배열을 탐색하고 각 garbage 총 개수를 더하면서 각  쓰레기 유형('M', 'P', 'G') 위치를 저장시킨다.
2. 각 쓰레기 유형의 마지막 위치에서 해당 누적 이동 시간을 더해주면 된다.

이번 문제에서는 어떻게 누적합을 구해야 할지 몰라서 다른 사이트를 참조했는데... 해당 쓰레기가 마지막으로 발생한 인덱스 위치 이 부분을 생각을 못해서 고민 하는데 시간이 많이 들었다.

Code

Python

class Solution:
    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:
        # 각 쓰레기 유형(M, P, G)의 마지막 위치를 저장하는 Map
        last_info = dict({})
        size = len(garbage)
        total_time = 0

        # 각 쓰레기 스테이션을 순회하며 쓰레기의 총 개수를 계산하고 마지막 위치를 기록
        for i in range(size):
            total_time += len(garbage[i])  # 현재 스테이션의 쓰레기 수를 추가
            for g in garbage[i]:
                last_info[g] = i # 쓰레기 유형의 마지막 위치 업데이트

        # 이동 시간의 누적 합을 계산하며 쓰레기 수거 시간을 추가
        prefix_sum = 0
        for i, t in enumerate(travel, 1):
            prefix_sum += t # 이동 시간의 누적 합 계산
            for last_index in last_info.values():
                if last_index == i: # 쓰레기 유형의 마지막 위치가 현재 인덱스와 일치하면
                    total_time += prefix_sum # 해당 쓰레기 수거에 필요한 이동 시간 추가

        return total_time

Java

class Solution {
    public int garbageCollection(String[] garbage, int[] travel) {
        
         // 각 쓰레기 유형(M, P, G)의 마지막 위치를 저장하는 Map
        Map<Character, Integer> lastInfo = new HashMap<>();
        int totalTime = 0;

        // 쓰레기 정보를 순회하며 총 쓰레기 수를 계산하고 마지막 위치 갱신
        for (int i = 0; i < garbage.length; i++) {
            String garbages = garbage[i];
            totalTime += garbages.length(); // 쓰레기 수 추가
            for (char g : garbages.toCharArray()) {
                lastInfo.put(g, i); // 쓰레기의 마지막 발생 위치 갱신
            }
        }

        // 이동 시간의 누적 합을 계산하며 각 쓰레기 유형의 마지막 위치까지의 시간 추가
        int accumulatedTravelTime = 0;
        for (int i = 0; i < travel.length; i++) {
            accumulatedTravelTime += travel[i]; // 현재까지의 이동 시간 합산
            for (char g : lastInfo.keySet()) {
                if (lastInfo.get(g) == i + 1) { // 마지막 위치가 현재 인덱스와 일치할 경우
                    totalTime += accumulatedTravelTime; // 해당 쓰레기에 필요한 이동 시간 추가
                }
            }
        }

        return totalTime;
    }
}