[프로그래머스][Java][Lv. 2] 택배 배달과 수거하기

문제 설명

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

 

---

 

제한 사항

 

---

 

입출력 예

 

---

 

풀이

import java.util.Stack;

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<>();
        
        int dZeroCount = 0, pZeroCount = 0;
        for (int i = 0; i < deliveries.length; i++) {
            if (deliveries[i] == 0) dZeroCount++;
            if (pickups[i] == 0) pZeroCount++;
            dStack.push(deliveries[i]);
            pStack.push(pickups[i]);
        }
        if (dZeroCount == dStack.size() && pZeroCount == pStack.size()) return 0;
        
        while (!(dStack.empty() && pStack.empty())) {
            answer += 2 * Math.max(dStack.size(), pStack.size());
            work(dStack, cap); // 배달
            work(pStack, cap); // 수거
        }
        return answer;
    }
    
    private void work(Stack<Integer> stack, int cap) {
        int tempCap = cap;
        
        while (!stack.empty()) {
            Integer i = stack.pop();
            tempCap -= i;
            if (tempCap <= 0)  {
                if (tempCap == 0) {
                   while (!stack.empty() && stack.peek() == 0) stack.pop(); 
                } else stack.push(-tempCap);
                break;
            }
        }
    }
}

 

---

 

후기

문제를 읽자마자 이건 스택으로 풀면 편하겠다고 생각했는데 대부분 그렇게 생각했는지 제출하고 보니까 스택으로 푼 사람이 많았다.

 

배달할 때에는 회수를 하면 도착할 때까지 계속 들고 있어야 하니 무조건 손해이고, 배달을 다 끝낸 뒤에 회수를 시작해야 한다. 적게 오가는 길이를 구하려면 처음부터 무조건 먼 곳부터 갔다 와야 하기 때문에 스택을 사용했다. 중간에 cap보다 큰 요소가 있으면 cap만큼 빼고 다시 추가하는 처리를 해주어야 한다.

 

중간에 자꾸 하나만 통과가 안 되길래 뭔가 보니까 배송과 수거의 요소가 전부 0이면 움직일 필요가 없으니 답이 0이다. 제한 사항에서부터 최소가 0이라 했는데 이 부분을 신경쓰지 못했다;; 다음에는 더 꼼꼼히 봐야겠다.