[그리디] 프로그래머스 택배 배달과 수거하기

byeol·2023년 6월 5일
0
post-thumbnail

문제 소개

택배 배달과 수거하기

  • n개의 집에 택배를 배달
  • 배달할 물건 모두 크기가 같은 재활용 택배 상자에 담아 배달
  • 배달을 다니면서 빈 재활용 택배 상자 수거
  • 트럭에는 재활용 택배 상자를 최대 cap개
  • 각 집마다 배달할 택배상자, 수거할 빈 택배상자의 개수가 주어진다.
  • 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동거리를 구하기
  • 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있다.

실패한 이유

문제를 어떻게 접근해야하는지 40분간 고민했지만
결국 Greedy로 끝집부터 수거해야한다는 방법, 그리고 각 조건에 대한
명확한 풀이가 떠오르지 않았습니다.

일단 문제에 주어진 첫 번째 예시에서 truck에 최대의 박스를 싣지 않고
수거할 수 있는 만큼만 싣는 것처럼 되어 있어서 그 부분에 대해서 구현하려고 오랜 시간을 썼습니다. 그러나 그 부분이 낚시?성 예시였던것 같습니다.

접근

첫 번째 예시

아래를 예시로 들어 접근 방법을 설명하겠습니다. (cap=4)

Stack을 이용합니다.

각 집마다 옮겨야하는 박스를 Stack에 넣고 넣을 때 각 집의 위치를 박스 수만큼 넣습니다.

마찬가지로 각 집마다 수거해야할 박스를 Stack에 넣고 넣을 때 각 집의 위치를 박스 수만큼 넣습니다.

이제 각 Stack에서 cap의 수만큼 함께 꺼냅니다.

각 Stack이 비어질 때까지 함께 꺼냅니다.
또한 처음 꺼낸 집의 위치 중에서 큰 것을 고릅니다. 왜냐하면 그 집이 처음에 들린 집이고 그 집부터 아래로 내려오면 택배를 주고 수거해야하기 때문입니다.

두 번째 예시

두 번째 예시의 경우 (cap=2)

아래의 모양을 가지게 됩니다.

예외상황

cap이 2인 경우

위와 같이 Pstack과 Dstack이 함께 파란색까지 진행되고 이후 Dstack이 남은 경우에는 남겨진 택배를 옮겨야하기 때문에 혼자서 진행됩니다.

풀이

import java.util.*;

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        
        //n개의 집에 택배를 배달
        // 배달할 물건 모두 크기가 같은 재활용 택배 상자에 담아 배달
        // 배달을 다니면서 빈 재활용 택배 상자 수거
        // 트럭에는 재활용 택배 상자를 최대 cap개
        // 각 집마다 배달할 택배상자, 수거할 빈 택배상자의 개수
        // 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동거리
        // 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있다.
        
        Stack<Integer> Dstack = new Stack<Integer>();
        Stack<Integer> Pstack = new Stack<Integer>();
        
        for(int i=0;i<n;i++){
            for(int j=0;j<deliveries[i];j++){
                Dstack.push(i+1);
            }
            for(int j=0;j<pickups[i];j++){
                Pstack.push(i+1);
            }
        }
        
        while(!Dstack.isEmpty() && !Pstack.isEmpty()){
            int Dhouse =Dstack.peek();
            int Phouse =Pstack.peek();
            
            for(int i=0;i<cap;i++){
                if(!Dstack.isEmpty()) Dstack.pop();
                if(!Pstack.isEmpty()) Pstack.pop();
            }
            
            
            answer+=Math.max(Dhouse,Phouse)*2L;
            
        }
        
        while(!Dstack.isEmpty()){
            int Dhouse =Dstack.peek();
            for(int i=0;i<cap;i++){
                if(!Dstack.isEmpty()) Dstack.pop();
            }
            answer+=Dhouse*2L;
        }
        
          while(!Pstack.isEmpty()){
            int Phouse =Pstack.peek();
            for(int i=0;i<cap;i++){
                if(!Pstack.isEmpty()) Pstack.pop();
            }
            answer+=Phouse*2L;
        }
        
        
        
        return answer;
    }
}
profile
꾸준하게 Ready, Set, Go!

0개의 댓글