[구현] - Lv2 - 택배 배달과 수거하기

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

프로그래머스

🌿 - 문제 설명

📌- 풀이

문제를 보고 역순으로 덱을 사용해서 풀면 편하겠다고 생각이 들었다.

 

가장 앞의 값이 0일 경우에는 굳이 들릴 필요가 없으므로 제거해주고 해당 cap만큼 덱의 가장 앞의 값부터 소거하면서 처리하는 방식으로

deliver 배열과 pickups배열 중 가장 큰 값을 기준으로 *2를 해서 더해주면 결과가 나온다.

 

여기서 문제점은 n이 10만일 경우 덱을 계속 추가 입력을 반복해줘야 하므로 시간도 그렇고 메모리도 많이 든다는 단점이 있다.

 

🔥 - Java 전체 코드

import java.util.*;
class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        Deque<Integer> dque = new ArrayDeque<>();
        Deque<Integer> pque = new ArrayDeque<>();
        
        for(int i = 0;i<n;i++){
            dque.addFirst(deliveries[i]);
            pque.addFirst(pickups[i]);
        }    

        while(!dque.isEmpty() || !pque.isEmpty() ){
            while(!dque.isEmpty() && dque.peek() == 0){
                dque.poll();
            }
            
            while(!pque.isEmpty() && pque.peek() == 0){
                pque.poll();
            }
            int dsize = dque.size();
            int psize = pque.size();
            int dcnt = cap;
            int pcnt = cap;
            while(dcnt > 0 && !dque.isEmpty()){
                if(dque.peek() <= dcnt){
                    dcnt -= dque.poll();
                }else{
                    dque.addFirst(dque.poll() - dcnt);
                    dcnt = 0;
                    
                }
            }
            while(pcnt >0 && !pque.isEmpty()){
                if(pque.peek() <= pcnt){
                    pcnt -= pque.poll();
                }else{
                    pque.addFirst(pque.poll() - pcnt);
                    pcnt = 0;
                }
            }
            
            answer += Math.max(dsize, psize) * 2;
            
        }
        
        return answer;
    }
}

 

 

처음에 이렇게 풀었는데, 시간과 메모리상 너무 비효율적이라는 생각이 들어서 다른 방법을 찾아봄

 

 

🔥 - 개선된 코드

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int deliver = 0, pickup = 0;
        for(int i = n-1; i >= 0; i--){
            deliver += deliveries[i];
            pickup += pickups[i];
            while (deliver > 0 || pickup > 0){
                deliver -= cap;
                pickup -= cap;
                answer += ((i+1) * 2);
            }

        }
        return answer;
    }
}

 

개선된 방식은 참고했는데, 배열의 마지막부터 해당 값을 cap만큼 빼주면서 택배차가 들릴지 말지 결정해서 answer에 더해주는 방식인데,

너무 간단하고 효율적이어서 다른 문제를 풀 때 참고하기 위해 가져왔다.