[JAVA] 프로그래머스 level2 택배 배달과 수거하기

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

프로그래머스

코딩테스트 연습 > 2023 KAKAO BLIND RECRUITMENT >  택배 배달과 수거하기

 

문제 접근

그리디? 스택? 문제이다. 

 

몇 가지 조건을 통해 문제를 해결했다. 

1. 항상 트럭에 실을 수 있는 재활용 택배 최대 개수만큼 트럭에 실는다. (cap)

2. 물류창고에서 가장 거리가 먼 집을 타겟으로 잡는다. 

3. 물류창고에서 가장 거리가 타겟은 배달/수거가 남은 집이다. 

4. 타겟에서 해결하고 남은 수량(배달 수량, 수거 가능 수량)각각 그다음 물류 창고에서 가장 먼 집에서 처리한다. 

 

스택 정의 

stack<int[]> stack  0 index: 거리 1 index: 수량, 재고 

stack1: deliveries

stack2: pickups

 Stack<int[]> stack1 = new Stack<>(); // deliveries
 Stack<int[]> stack2 = new Stack<>(); // pickups

 

스택에 값 넣기 

값이 0이면 pass

for(int i = 0; i < n; i++){
    if(deliveries[i] != 0) stack1.add(new int[]{i+1, deliveries[i]});
    if(pickups[i] != 0) stack2.add(new int[]{i+1, pickups[i]});
}

 

변수 정의하기

long answer = 0;  // return 정답 

int cap1 = 0 ; //  택배 트럭 수량(배달 용도)

int cap2 = 0 ; //  택배 트럭 수량(수거 용도) 

 

 

핵심 로직 

while(!stack1.isEmpty() || !stack2.isEmpty()) 집에 배달 or 수거할 재고가 모두 사라질 때 까기 반복 

 

cap1 = cap; //  배달 가능 숫자 cap( 택배 트럭 수량 )으로 초기화 

cap2 = cap; //  수거 가능 숫자  cap( 택배 트럭 수량 )으로 초기화 

 

case1,2,3

 

case1 : 배달, 수거 재고 둘 다 남아있는 상태

case2 : 배달 재고만 남아있는 상태 

case3 : 수거 재고만 남아있는 상태 

 

case1

answer += (stack1.peek()[0] >= stack2.peek()[0] ? stack1.peek()[0] : stack2.peek()[0]) * 2;

배달이 남은 집 거리 vs 수거가 남은 집 거리 더 먼 거리를 가야 한다. 

 

case2

배달만 남아 있으니까 배달이 남아있는 집중 가장 먼 거리에 가야 한다. 

cap2 = 0; 수거 수량은 필요 x 

 

case3

수거만 남아 있으니까 수거수량이 남아있는 집중 가장 먼 거리에 가야 한다. 

cap1 = 0; 배달 수량은 필요 x 

 

cap1, cap2 (처리 가능한 수량) 가 모두 사라지거나 stack이 빈다고 하면(더이상 일이 있는 집이 없다면) 종료 

ex) 배달 수량 

while(cap1!=0 && !stack1.isEmpty()){
    int [] temp = stack1.pop();
    if(cap1 >= temp[1]){
        cap1 -= temp[1];
    }
    else{
        temp[1] -= cap1;
        cap1 = 0; // break;
        stack1.push(temp);
    }
}

 

while(!stack1.isEmpty() || !stack2.isEmpty()){ // 배달 or 수거 재고 모두 사라질 때까지 반복 
    cap1 = cap;
    cap2 = cap;

    if(!stack1.isEmpty() && !stack2.isEmpty()){ // 배달, 수거 재고 둘 다 남아있는 상태
        answer += (stack1.peek()[0] >= stack2.peek()[0] ? stack1.peek()[0] : stack2.peek()[0]) * 2;
    }
    else if(!stack1.isEmpty()){ // 배달 재고만 남아있는 상태 
        answer += (stack1.peek()[0]) * 2; 
        cap2 = 0;
    }
    else{ // 수거 재고만 남아있는 상태 
        answer += (stack2.peek()[0]) * 2; 
        cap1 = 0;
    }

    while(cap1!=0 && !stack1.isEmpty()){
        int [] temp = stack1.pop();
        if(cap1 >= temp[1]){
            cap1 -= temp[1];
        }
        else{
            temp[1] -= cap1;
            cap1 = 0; // break;
            stack1.push(temp);
        }
    }

    while(cap2!=0 && !stack2.isEmpty()){
        int [] temp = stack2.pop();
        if(cap2 >= temp[1]){
            cap2 -= temp[1];
        }
        else{
            temp[1] -= cap2;
            cap2 = 0; // break;
            stack2.push(temp);
        }
    }
}

전체 코드

import java.util.*;
class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        
        Stack<int[]> stack1 = new Stack<>(); // deliveries
        Stack<int[]> stack2 = new Stack<>(); // pickups
        
        // 거리가 가장 먼 순서대로 처리하기 위해서 해당 순서로 스택에 넣기 
        // 0: 거리 1: 재고 
        for(int i = 0; i < n; i++){
            if(deliveries[i] != 0) stack1.add(new int[]{i+1, deliveries[i]});
            if(pickups[i] != 0) stack2.add(new int[]{i+1, pickups[i]});
        }
        int cap1 = 0;
        int cap2 = 0;
        
        long answer = 0;
        while(!stack1.isEmpty() || !stack2.isEmpty()){ // 배달 or 수거 재고 모두 사라질 때까지 반복 
            cap1 = cap;
            cap2 = cap;
            
            if(!stack1.isEmpty() && !stack2.isEmpty()){ // 배달, 수거 재고 둘 다 남아있는 상태
                answer += (stack1.peek()[0] >= stack2.peek()[0] ? stack1.peek()[0] : stack2.peek()[0]) * 2;
            }
            else if(!stack1.isEmpty()){ // 배달 재고만 남아있는 상태 
                answer += (stack1.peek()[0]) * 2; 
                cap2 = 0;
            }
            else{ // 수거 재고만 남아있는 상태 
                answer += (stack2.peek()[0]) * 2; 
                cap1 = 0;
            }
            
            while(cap1!=0 && !stack1.isEmpty()){
                int [] temp = stack1.pop();
                if(cap1 >= temp[1]){
                    cap1 -= temp[1];
                }
                else{
                    temp[1] -= cap1;
                    cap1 = 0; // break;
                    stack1.push(temp);
                }
            }
            
            while(cap2!=0 && !stack2.isEmpty()){
                int [] temp = stack2.pop();
                if(cap2 >= temp[1]){
                    cap2 -= temp[1];
                }
                else{
                    temp[1] -= cap2;
                    cap2 = 0; // break;
                    stack2.push(temp);
                }
            }
        }
        return answer;
    }
}