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

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

프로그래머스

생각의 흐름

생각이고 나발이고 문제 진짜 어렵다 생각 드는데, 이거 나처럼 greedy라고 생각 못한 사람은 끝까지 이 문제 못 건들이다가 끝났을것 같다.

 

일단 N제한이 100,000 이라 O(N^2), 즉 완전 탐색은 절대 안된다 생각했다.

여기서 문제다.

그럼 O(logN) = 5, O(NlogN) = 500,000, O(N) = 1000,000 이 가능 할탠데....

뭔가 정렬되 있는 순차 중에서 탐색을 하는 느낌은 아니라, O(logN)의 이진탐색 방식은 아닐꺼라 생각했고...

남은 O(NlogN) = 500,000, O(N) = 1000,000 중 하난데...

 

여기서 부터 계속 특정 알고리즘만 생각하다 Greedy 라는 점은 알아차리지 못했다.

(평소 탐욕 문제 잘 안풀어본 업보 인 것 같다)

 

이 문제를 위한 greedy 전략은 다음과 같습니다.

1. 배달 및 수거할 택배 상자가 남은 가장 먼 집부터 택배를 배달 및 수거합니다.
2. 트럭이 물류창고에서 출발해 가장 먼 집으로 이동할 때는 배달만 하고, 다시 물류창고로 돌아올 때는 수거만 합니다.
3. 트럭이 물류창고에서 출발할 때 항상 택배를 최대 개수만큼 배달하고, 물류창고로 돌아갈 때 최대 개수만큼 수거합니다.

왕복 한번을 하나의 반복문이라 생각하고, 하나의 loop안에서 배달 한번, 수거 한번을 진행한후 이를 반복하면 됩니다.

 

나의 코드

import java.util.*;

class Solution {
    
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        
        Stack<Info> go = new Stack<>();
        Stack<Info> back = new Stack<>();
        
        for(int i = 0; i < n; i++) {
            if(deliveries[i] > 0) {
                go.push(new Info(i + 1, deliveries[i]));
            }
            
            if(pickups[i] > 0) {
                back.push(new Info(i + 1, pickups[i]));
            }
        }
        
        while(!go.isEmpty() || !back.isEmpty()) {            
            int goLen = go.isEmpty() ? 0 : go.peek().houseNumber;
            int backLen = back.isEmpty() ? 0 : back.peek().houseNumber;
            if(goLen > backLen) {
                answer += goLen * 2;
            } else {
                answer += backLen * 2;
            }
            
            int box = 0;
            while(!go.isEmpty() && box <= cap) {
                if(cap >= go.peek().cnt + box) { // 모두 배달 가능한 경우
                    box += go.peek().cnt;
                } else { // 일부 배달 가능한 경우
                    go.peek().cnt -= (cap - box);
                    break;
                }
                go.pop();
            }
            
            box = 0;
            while(!back.isEmpty() && box <= cap) {
                if(cap >= back.peek().cnt + box) {
                    box += back.peek().cnt;
                } else {
                    back.peek().cnt -= (cap - box);
                    break;
                }
                back.pop();
            }      
        }
        
        return answer;
    }
    
    static class Info {
        public int houseNumber;
        public int cnt;
        
        public Info(int houseNumber, int cnt) {
            this.houseNumber = houseNumber;
            this.cnt = cnt;
        }
    }
}