[프로그래머스] 택배 배달과 수거하기 (Lv2)

date

Sep 24, 2023

slug

programmers-delivery-and-pickup

author

status

Public

문제 링크

school.programmers.co.kr

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

문제 설명

제한사항

1 ≤ cap ≤ 50

1 ≤ n ≤ 100,000

deliveries의 길이 = pickups의 길이 = n

deliveries[i]는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.
pickups[i]는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.
0 ≤ deliveries의 원소 ≤ 50
0 ≤ pickups의 원소 ≤ 50

트럭의 초기 위치는 물류창고입니다.

문제 해설

최적화 이전(스택으로 풀기)

1. 아이디어

갈 때 배달, 올 때 수거

한 번 갈 때 최대의 거리만 알면 x2

1트) 배달, 수거를 스택으로 저장해두고 뺄까? -> 이러면 스택 만들기에만 50*100,000 번의 연산 필요 -> 최대한 주어진 배열 데이터로 사용하자

2트) 현재 확인해야 할 최대 거리를 글로벌로 저장하고, 갈 때마다 갱신

k = 현재 확인해야 할 최대 거리의 집
curDeliveryCap : 현재 배달에서 배달 가능한 남은 개수
curPickCap : 현재 배달에서 수거 가능한 남은 개수
k 부터 하나씩 줄여나가기
배달 가능 개수 없으면 여기서 멈추고 curDeliveryMax
픽업 가능 개수 없으면 여기서 멈추고 curPickMax
k 를 이동 거리에 추가
둘 중 더 큰 값으로 k 갱신 -> 이렇게 하면 불필요한 연산이 많음(이미 수거, 배달할 곳이 없는 집도 계속 중복 확인해야함)..

불필요한 중복 확인을 없애는 게 더 중요하니까.. 일단 스택으로 해볼까?

2. 시간복잡도

스택 채우기 : O(100,000 * 50) ~= O(n)

배달하기 : O(n)

O(n)

스택 채우는 부분이 비효율적임..

3. 자료구조

Stack<Integer> deliveryList, pickupList : 배달/수거 리스트

int delMax, pickMax : 현재 배달에서 가야 할 최대 거리

코드


import java.util.*;
import java.io.*;

class Solution {
    public static Stack<Integer> deliveryList;
    public static Stack<Integer> pickupList;
    
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        // 두 스택 생성
        deliveryList = new Stack<Integer>();
        pickupList = new Stack<Integer>();
        // 스택 채우기
        for(int i = 1; i <= n; i++) {
            // 각 집의 배달/수거 개수만큼 집 숫자 넣기
            for(int j = 0; j < deliveries[i-1]; j++) {
                deliveryList.push(i);
            }
            for(int j = 0; j < pickups[i-1]; j++) {
                pickupList.push(i);
            }
        }
        
        long totalDistance = 0;
        // 둘 다 빈 스택이 때까지
        while(!(deliveryList.isEmpty() && pickupList.isEmpty())) {
            // 둘 중 더 먼 곳으로 시작
            int delMax = deliveryList.isEmpty()?0:deliveryList.peek();
            int pickMax = pickupList.isEmpty()?0:pickupList.peek();
            int curDistance = Math.max(delMax, pickMax);
            totalDistance += Long.valueOf(curDistance);
            //System.out.println(delMax+", "+pickMax+" => "+curDistance + " 만큼 가기");
            
            // 가능한만큼 배달/수거
            for(int i = 0; i < cap; i++) {
                if(deliveryList.isEmpty()) break; // 더이상 배달할 곳이 없으면 끝
                deliveryList.pop();
            }
            for(int i = 0; i < cap; i++) {
                if(pickupList.isEmpty()) break; // 더이상 수거할 곳이 없으면 끝
                pickupList.pop();
            }
            

        }
        
        long answer = totalDistance * 2;
        return answer;
    }
}

나름의 최적화(포인터)

initialize 부분에서 스택 채우는 데에 시간이 너무 많이 쓰이고 비효율적이라고 판단되어서.. 포인터를 이용해서 deliveries, pickups 를 그대로 사용하는 방법은 없을지 고민

well-made 풀이

아래 코드에서 중요한 부분은 while 부분이다.


class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = -1;
        int deliver = 0, pickup = 0; // 현재 포인터에서 배달/수거할 개수
        for(int i = n-1; i >= 0; i--){
            deliver += deliveries[i];
            pickup += pickups[i];
						// 둘 중 하나라도 해야 한다면 여기 방문(최대 거리)
						// deliver, pickup 값이 음수라면 이곳은 이미 배달/수거를 했으니 갈 필요가 없다는 뜻
						// 양수라면 이곳에서 배달/수거를 해야 하니 그만큼 배달/수거를 하겠다는 의미
            while (deliver > 0 || pickup > 0){
								// 방문했으니 cap만큼은 다 하고 돌아갑니다
                deliver -= cap;
                pickup -= cap;
								// 이 곳에 방문했음을 의미(거리 갱신)
                answer += ((i+1) * 2);
            }

        }
        return answer + 1;
    }
}

내 코드와 웰메이드 코드의 시간복잡도 차이..🥲

스택 초기화, peek, poll에서 오는 불필요한 연산