문제

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

풀이

트럭으로 배달할 때 최대 용량 만큼 배달하고 최대 용량 만큼 수거하여 이동 거리가 최소가 되도록하는 방법을 구해야 한다.

간단하게 생각해보면 최대 개수 만큼 들고 가장 먼 지점에 배달 후 돌아올 때 최대 개수 만큼 수거하는 방식이다.

이 방식은 가장 먼 지점에 대해 배달/수거를 완료했다면 그 지점은 두 번 다시 고려하지 않아도 되므로 그리디라는 것을 알 수 있다. 가장 먼 지점부터 배달/수거하는 것이 최적의 해라는 것이다.

1. 먼저 배달, 수거해야 할 위치를 기록하고 완료된 지점은 다시 방문하지 않아도 되므로 제거하기 위해 Stack으로 구현을 하였다.

		Stack<Integer> go = new Stack<>(); // 배달
        Stack<Integer> back = new Stack<>(); // 수거

        for(int i = 0; i < n;i ++){
            if(deliveries[i] != 0){
                go.add(i);
            }
        }

        for(int i = 0; i < n;i ++){
            if(pickups[i] != 0){
                back.add(i);
            }
        }

2. 그 후 배달/수거 둘 중 하나라도 남아있다면 왔다-갔다를 계속 해야하므로 while문을 통해 하나라도 남아있다면 수행을 해주었다.

   이 때 배달/수거 중 더 먼 지점 x 2를 하여 이동 거리를 더해줘야 한다.

 		while(!go.isEmpty() || !back.isEmpty()){
            int goPos = 0;
            if(!go.isEmpty()){
                goPos = go.peek();
            }

            int backPos = 0;
            if(!back.isEmpty()){
                backPos = back.peek();
            }

            int maxPos = Math.max(goPos, backPos); // 이동 거리는 배달/수거 중 가장 먼 거리 x 2
            answer += (maxPos + 1) * 2;

그리고 최대 배달/수거 개수(cap) 만큼 현재 배달/수거 해야하는 개수에서 빼주면 한 번의 이동(왔다-갔다)을 완료한 상태가 된다.

이 경우 두 가지 케이스로 나뉜다

1. 택배를 더 많이 가져와 배달을 더 할 수 있는 경우(pop을 하고 남아있는 택배를 나눠줌)
2. 택배를 부족하게 가져와 한 번 더 들러야 하는 경우(pop을 하지 않고 가져온 택배 만큼 개수를 빼줌)

				if(goCnt <= cnt){ // 더 많이 가져왔을 때 cnt가 남아있으므로 또 나눠줄 수 있음
                    go.pop(); // 방금 방문한 지점은 더 이상 고려 x(deliveries[idx] = 0 생략)
                    cnt -= goCnt;
                }
                else{// 한 번 더 들러야 하는 경우 
                    deliveries[idx] -= cnt;
                    cnt = 0;
                }

이 과정을 반복하여 배달/수거를 완료할 때까지(Stack이 둘다 empty일 때까지) 반복하면 우리가 원하는 최소 이동 거리를 구할 수 있다.

그리디라는 것을 깨닫고 구현하였지만 바로 와닿지는 않았던 문제였다.
그래도 방향성을 정하고 문제를 풀었는데 while(!go.isEmpty() || !back.isEmpty()) 코드에서 ||를 &&라고 적어 한참을 헤맸다. 풀이를 떠올리고 떠올렸으면 풀이를 코드로 구현하는 것을 연습하는 문제였다.

코드

public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        Stack<Integer> go = new Stack<>(); // 배달
        Stack<Integer> back = new Stack<>(); // 수거

        for(int i = 0; i < n;i ++){
            if(deliveries[i] != 0){
                go.add(i);
            }
        }

        for(int i = 0; i < n;i ++){
            if(pickups[i] != 0){
                back.add(i);
            }
        }


        while(!go.isEmpty() || !back.isEmpty()){
            int goPos = 0;
            if(!go.isEmpty()){
                goPos = go.peek();
            }

            int backPos = 0;
            if(!back.isEmpty()){
                backPos = back.peek();
            }

            int maxPos = Math.max(goPos, backPos); // 이동 거리는 배달/수거 중 가장 먼 거리 x 2
            answer += (maxPos + 1) * 2;

            int cnt = cap;
            while(!go.isEmpty() && cnt > 0){
                int idx = go.peek();
                int goCnt = deliveries[idx];
                if(goCnt <= cnt){ // 더 많이 가져왔을 때
                    go.pop();
                    cnt -= goCnt;
                }
                else{// goCnt > cnt
                    deliveries[idx] -= cnt;
                    cnt = 0;
                }
            }

            cnt = cap;
            while(!back.isEmpty() && cnt > 0){
                int idx = back.peek();
                int backCnt = pickups[idx];
                if(backCnt <= cnt){
                    back.pop();
                    cnt -= backCnt;
                }
                else{
                    pickups[idx] -= cnt;
                    cnt  = 0;
                }
            }
        }

        return answer;
    }