[Lv.2] 택배 배달과 수거하기

95/100 코드

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {

        int ep=getEndPoint(n-1, deliveries, pickups);
        long answer=0;
        int startIdx=0;
        while (true){
            if(ep<0){
                break;
            }
            int load=cap;
            int leftPickUp=cap;
            int dis=2*(ep+1);

            for(int i=ep;i>=startIdx;i--){
                //int idx=ep-i+startIdx; // 1회차:0 2회차:1
                if(deliveries[i]!=0){
                    //해당 집의 배달이 완료되지 않은 경우.
                    if(load>0){
                        int leftDelivery=deliveries[i];
                        if(load<leftDelivery){
                            //3개들고왔는데 4개 줘야하는 경우
                            deliveries[i]-=load;
                            load=0;
                        }else if(load==leftDelivery){
                            deliveries[i]-=load;
                            load=0;
                        }else{
                            deliveries[i]=0;
                            load-=leftDelivery;
                        }
                    }
                }
                if(pickups[i]!=0){
                    //원래는 배달을 다 간 후 수거를 가는 for문을 작성해야겠지만
                    //사실 배달은 항상 마지막집으로 가는 거고 마지막집에 도착했다면 그 때 택배차는 비어있다.
                    //즉, 동시에 확인해도 된다.
                    if(leftPickUp>0){
                        int leftPick=pickups[i];
                        if(leftPickUp<leftPick){
                            //3개 더 실을 수 있는데 해당 집은 4개를 수거해야 하는 경우
                            pickups[i]-=leftPickUp;
                            leftPickUp=0;
                        }else if(leftPickUp==leftPick){
                            pickups[i]-=leftPickUp;
                            leftPickUp=0;
                        }else{
                            pickups[i]=0;
                            leftPickUp-=leftPick;
                        }
                    }
                }
                if(load==0&&leftPickUp==0) {
                    break;
                }
                if(deliveries[startIdx]==0&&pickups[startIdx]==0){
                    //현재 검사 시작점의 값이 0으로 바뀜 -> 새로운 검사 시작점 설정
                    for(int j=startIdx;j<ep;j++){
                        if(deliveries[j]!=0||pickups[j]!=0){
                            startIdx=j;
                            break;
                        }
                    }
                }
                if(startIdx>=ep)
                    break;

            }

            ep= getEndPoint(ep, deliveries, pickups);
            answer+=dis;
        }
        return answer;
    }
    private static int getEndPoint(int beforeEp, int[] deliveries, int[] pickups) {
        int ep=-1;
        for (int i = beforeEp; i>=0; i--){
            if(deliveries[i]!=0) {
                ep = i;
                break;
            }
            if(pickups[i]!=0) {
                ep =i;
                break;
            }
        }
        return ep;
    }
}

통과 코드 (여기를 참조했습니다.)

import java.util.Stack;

public class Solution {

    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        Stack<Integer> dStack = new Stack<>();
        Stack<Integer> pStack = new Stack<>();

        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 lastD = dStack.peek();
            int lastP = pStack.peek();

            for (int i = 0; i < cap; i++) {
                if (!dStack.isEmpty()) dStack.pop();
                if (!pStack.isEmpty()) pStack.pop();
            }

            answer += Math.max(lastD, lastP) * 2L;
        }

        while (!dStack.isEmpty()) {
            int last = dStack.peek();

            for (int i = 0; i < cap; i++) {
                if (!dStack.isEmpty()) dStack.pop();
            }

            answer += last * 2L;
        }

        while (!pStack.isEmpty()) {
            int last = pStack.peek();

            for (int i = 0; i < cap; i++) {
                if (!pStack.isEmpty()) pStack.pop();
            }

            answer += last * 2L;
        }

        return answer;
    }
}

---

문제를 보자마자 그리디로 풀면 되겠네 ~ 했는데 제출하니 우수수 틀렸었다.

그래도 접근법이 크게 틀리진 않아서 몇분만에 로직 수정해서 제출하니 95점이 나왔다

문제는 여기부터였다..

단 하나 안되던 17번 테스트 케이스는 시간초과가 원인이였고, 난 그걸 해결하려고 첫 점도 같이 갱신해보고 끝점 후보를 LinkedHashSet을 이용해 넣어보려고도 했는데 한문제잡고 두시간이 넘어가니 머리가 어지러워 그냥 통과한 코드를 참조해보기로 했다.

 

그리디를 이용해 푸는 문제는 정확히 맞았고 푸는 방식도 얼추 맞았지만..

n번의 for-Loop안에서 스택을 이용하여 배달가야하는 곳의 인덱스를 배달 갯수만큼 저장하고 이걸 그냥 빌때까지 pop하며 단순히 거리만 더하면 되는 문제였다.

 

스택을 사용하는 문제를 오랜만에 봐서 스택을 쓰면 된다는 걸 애초에 떠올리질 못했다. 다음부턴, 꼭 queue,set,map,list..말고도 stack도 사용해보자 !