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

문제

카카오 2023 기출

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

프로그래머스

알아야 할 개념

• 그리디 접근법 
• 자바 링크드 리스트

풀이

예제를 읽으면 감이 올 것이다. 무조건 0보다 크고, 마지막 번째부터 탐색해줘야 한다. 

풀이는 다음과 같다. 

1. [ 개수, 거리 ] 정보를 포함한 링크드 리스트 2개를 만든다. 
2. 개수 > 0 인 것들만 리스트에 추가한다.
3.  현재 용량 < max 용량 조건을 만족하면 계속 리스트의 마지막 원소를 뽑아 더해준다. 
4. 리스트 1 , 2 중 더 긴 dist 를 answer 에 추가한다.
5. 답을 리턴한다. 

코드

import java.util.*;

class Solution {
    public long solution(int cap, int n, int[] d, int[] p) {
        
        long answer = 0;
        int len = d.length;
        //val, idx
        LinkedList<int[]> l1 = new LinkedList<>();
        LinkedList<int[]> l2 = new LinkedList<>();
        for(int i =0 ;i < len; i++){
            if(d[i] > 0)
                l1.add(new int[]{d[i], i+1});
            if(p[i] > 0)
                l2.add(new int[]{p[i], i+1});
        }
        int sum =0 ;
        int dist = 0;
        while(!l1.isEmpty() || !l2.isEmpty()){
            sum =0;
            dist = 0;
            while(!l1.isEmpty() && sum < cap){
                int[] c = l1.pollLast();
                dist = Math.max(dist, c[1]);
                
                if(c[0] + sum <= cap){
                    sum +=c[0];
                }else{
                    c[0] -= (cap - sum);
                    l1.add(c);
                    break;
                }
            }
            sum = 0;
            while(!l2.isEmpty() && sum < cap){
                int[] c = l2.pollLast();
                dist = Math.max(dist, c[1]);
                
                if(c[0] + sum <= cap){
                    sum +=c[0];
                }else{
                    c[0] -= (cap - sum);
                    l2.add(c);
                    break;
                }
            }
            answer += dist*2;
        }
        
        return answer;
    }
}