[Programmers] 택배 배달과 수거하기 / ❌

프로그래머스

 

1. 제출코드 (1시간 10분 23초 / Stack)

import java.util.*;

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        ArrayDeque<Integer> d = new ArrayDeque<>();
        ArrayDeque<Integer> p = new ArrayDeque<>();
        
        for(int i = 0; i < deliveries.length; i++) {
            d.add(deliveries[i]);
        }
        for(int i = 0; i < pickups.length; i++) {
            p.add(pickups[i]);
        }
        
        while(!d.isEmpty() || !p.isEmpty()) {
            int dist = 0;
            int stock = cap;
            while(!d.isEmpty()) {
                int t = d.pollLast();
                if(t == 0) continue;
                if(stock >= t) {
                    stock -= t;
                    dist = Math.max(dist, d.size() + 1);
                } else if (stock < t) {
                    t -= stock;
                    d.add(t);
                    dist = Math.max(dist, d.size());
                    break;
                }
            }
            int store = 0;
            while(!p.isEmpty()) {
                int t = p.pollLast();
                if(t == 0) continue;
                if(store + t <= cap) {
                    store += t;
                    dist = Math.max(dist, p.size() + 1);
                } else if(store + t > cap){
                    t = store + t - cap;
                    p.add(t);
                    dist = Math.max(dist, p.size());
                    break;
                }
            }
            answer += dist * 2;
        }
        return answer;
    }
}

 

 

2. 구현 로직

1. 배달 Stack과 수거 Stack을 만들어 모든 집의 정보를 입력
2. 2개의 스택이 모두 빌 때까지 반복
   1. 가장 먼 집에서부터 하나씩 배달을 진행하고 dist를 지속적으로 갱신(모든 상자를 배달할 때까지 반복)
   2. 가장 먼 집에서부터 하나씩 수거를 진행하고 dist를 지속적으로 갱신(상자가 Cap만큼 찰 때까지 반복)
   3. 왕복이므로 dist*2를 하여 answer에 더하기

 

3. 유의할 점

• 시간 복잡도를 계산하지 않았어서 배열을 그대로 활용했더니 16,17,18,19 케이스에서 시간초과가 터졌다.
• 이를 해결하기 못해서, 질문하기를 보니 Stack을 활용한다는 것을 보고 알고리즘을 다시 작성해서 풀 수 있었다.