택배 배달과 수거하기(java)

NJW·2023년 5월 2일

코테

목록 보기

158/170

문제 설명

문제가 너무 복잡하다...

아무튼 대략 설명을 해보자면 일렬로 나열된 n개의 집이 있다고 가정한다. 이때 각 집에는 배달되어야 할 상자와 수거되어야 할 상자의 수가 존재한다. 택배 트럭이 cap만큼의 상자를 옮길 수 있을 때 모든 집들의 택배를 배달하고 수거할 최단 거리를 구하는 문제다.

짧게 설명하기 위해 굉장히 압축되어 있는데 이 문제는 예시를 따라가면서 봐야 이해하기 쉬울 것이다.

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

문제 풀이

첫 번째 접근

문제를 보고 나서 든 생각! 이게 뭔데? 처음에는 알고리즘과 연관지어서 접근해보려고 했다.

보니까 제일 뒤에서부터 시작해야 최소 값이 나오는 거 같고... 그렇다면 제일 뒤에서부터 cap가 허용하는 곳까지 택배 상자를 배달하면 되니까 슬라이딩 윈도우?

그래서 처음 접근은 start와 end를 사용해서 슬라이딩 윈도우 방식을 써봤다. 그리고 택배 수거는 올때 하면 되니까 총 합이 cap 이상일 때만 수거해서 오면 되고. 길이는 왕복이니까 end x 2를 계속 더해주면 되고.

뭐 이론적으로는 나쁘지 않았는데, 문제는 내가 슬라이딩 윈도우를 정확하게 못 쓴다는 거다. 엉... 그래서 제대로 코드를 짜지 못했다.

그리고 나서 생각한 게 스택이다. 맨 뒤에서부터 하니까 스택에 값을 넣어두고 pop해서 더한다음에 cap와 비교하고...

그러나 이 생각도 여기까지! 왜냐! 지금은 거의 밤 12시가 다 되어가고(문제를 풀 당시에는) 너무 피곤해서 머리가 제대로 안 돌아갔다. 그러므로 스택을 이용한 다른 사람의 풀이를 봤다.

두 번째 접근

다른 사람의 풀이에서는 스택을 총 두 개를 썼다. 하나는 배달용, 다른 하나는 수거용.

여기서 반복문을 쓸 때는 두 개 다 empty가 나와야 하므로 적어도 하나가 차 있으면 반복문이 돌아야 한다. 그러므로 or을 써야 한다.

일단 맨 끝이 0일 경우 굳이 검사할 필요가 없으니 해당 값은 pop한다. 그리고 배달 스택과 수거 스택 중 더 긴 값을 찾아서 2를 곱해준다. 2를 곱해주는 건 왕복이기 때문에 그렇다. 또한 배달이든 수거든 커버할 수 있어야 하기에 더 긴 값을 더해준다.

그리고 배달를 하나씩 pop해줘서 cap보다 클 때까지 더해준다. cap이하라는 의미는 배달 가능이라는 뜻. 그 반대는 배달 불가능이라는 의미로 남은 값은(더한 값에 cap 뺀 거) 스택에 넣어주고 break를 한다.

수거도 배달과 마찬가지로 움직인다.

이렇게 하면 문제를 풀 수 있다.

코드

java

import java.util.*;

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        Stack<Integer> D = new Stack<>();
        Stack<Integer> P = new Stack<>();
        long answer = 0;
        
        for(int i=0; i<n; i++){
            D.push(deliveries[i]);
            P.push(pickups[i]);
        }
        
        //둘 중 하나라도 참이면 계속 굴러간다.
        while(!D.isEmpty() || !P.isEmpty()){
            
            //맨 끝이 0일 경우 계산할 필요 없으니 pop
            while(!D.isEmpty() && D.peek() == 0){
                D.pop();
            }
            while(!P.isEmpty() && P.peek() == 0){
                P.pop();
            }
            
            answer += 2*Math.max(D.size(), P.size());
            
            int Dtarget = 0;
            while(!D.isEmpty()){
                int Dcurrent = D.pop();
                
                if(Dtarget + Dcurrent <= cap){
                    //배달 가능
                    Dtarget += Dcurrent;
                }else{
                    //배달 불가능
                    //남은 배달 양 스택에 넣어주기
                    D.push(Dtarget + Dcurrent - cap);
                    break;
                }
            }
            
            int Ptarget = 0;
            while(!P.isEmpty()){
                int Pcurrent = P.pop();
                
                if(Ptarget + Pcurrent <= cap){
                    Ptarget += Pcurrent;
                }else{
                    P.push(Ptarget + Pcurrent - cap);
                    break;
                }
            }
        }
        
        return answer;
    }
}