프로그래머스 (카카오 기출) | LV.2 택배 배달과 수거하기 - 그리디 문풀 (Java)

⬛ 프로그래머스 (카카오 기출) | LV.2 택배 배달과 수거하기 

2023 카카오 블라인드 Recruitment 기출

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

프로그래머스

문제 설명 1

문제 설명 2

---

💚문제 접근 방식

솔직히 문제만 읽었을 때 내용이 확 와닿지는 않는다. 그리고 문제 내용을 이해해도 코드 구현 시 최대한 효율적으로 처리할 수 있도록 고민해야 해서 이런 류의 문제는 계속 연습해야 할 것 같다. 직접 푸는 건 실패했고, 이해한 내용을 토대로 정리했다.

• 최소 이동 거리를 구하는 게 목표인 문제이고, 택배 차는 한 번에 cap 개만큼만 담을 수 있다.
• 한 번에 최대한 많이 배달/수거해서 모두 처리한 전체 거리가 최소가 되도록 해야 한다.
• 예시를 보면 알 수 있지만, 뒷집부터 역순으로 배달/수거를 최대한 많이 하면서 거꾸로 와야 최소거리가 된다.
• 뒷집을 먼저 처리하고나면 이후 뒷집까지 또 방문할 이유가 없으니, 전체 이동 거리를 최소로 만들 수 있기 때문이다.

→ 그리디 개념이 활용되는데, 현재 상황에서 가장 뒤쪽 집부터 최대한 배달/수거를 많이 하는 것이 매 상황에서는 최선이다. ‘이왕 멀리까지 간 김에 몰아서 처리하자’는 소리다.

1) 문제 이해

최대한 뒤쪽 집부터 털면서 배달/수거하고, cap 개수 용량 넘치지 않도록 처리 후 물류까지 와야 한다.

(논리적 개념) 물류→집 방향으로 배달하고, 집→물류 방향으로 수거하자.

예제 2의 경우, cap = 2 이다. 즉, 한 번 차로 실을 수 있는 용량 최대 2개라는 거다.

첫 번쨰 왕복
처음엔 (물류-> 집) 7번째 집에서 2개의 택배를 배달한다. (애초에 2개 최대로 실으니까)
이후 (집-> 물류) 돌아가는 길에 6번쨰 집의 택배 2개를 수거한다. 이제 용량 꽉차서 더 처리 못하니 물류까지 온다.거리 : (7X2) 

두 번째 왕복
앞선 처리에서 6번째 집까진 처리가 된 상태이다. 이제 5번째 집까지만 보면 된다. 

(물류->집) 방향으로 갈 때 어차피 cap=2 이므로 2개 들고 가서 3번째 집 1개 배달, 5번째 집까지 가서 거기에 1개의 배달 처리한다. 
(집-> 물류) 방향으로 돌아갈 때, 4번째 집 1개, 2번째 집 1개씩 수거하면 cap 용량 꽉차므로 이제 다시 물류까지 감.
거리 : (5X2) 

세 번째 왕복
이제 3번째 집까지만 보면 된다. (3번째 집에 배달해야 할 용량 1개 남아있으니) 
(물류-> 집) 방향으로 cap=2만큼 들고 1번째 집 1개, 3번째 집 1개씩 배달 처리 완료
(집-> 물류) 방향으로 2번째 집에 남아있던 수거 1개 해서 되돌아오면 '모든 배달/수거 완료' 상태가 된다.
거리 : (3X2) 

결과적으로 전체 최소 거리 30으로 모든 택배/수거 가능하게 된다.
-> 이런 논리적 흐름으로 문제가 진행된다는 사실을 이해하고 넘어가자. 

---

2) 코드 풀이 이해

위 내용대로 이해는 했지만, 이중 for문을 돌면서 모든 집에 대해 처리를 왔다갔다 하려고 한다면 시간 초과가 난다.

 //이중 for 문 돌면 시간 초과나기 때문에 최대한 뒤쪽부터 차례로 돌고, 매번 그리디 적으로, (현재 i+1) 집에 있는 상황에서 최대한 배달/수거를 몰아서 처리할 거다. (이후에 방문 안하도록)

deliveries[i] : i+1 번째 집에 배달할 택배 상자 개수
pickups[i] : i+1 번째 집에서 수거할 택배 상자 개수 

d_cap : 특정 지점에서 배달 해줘야 할 개수
p_cap : 특정 지점에서 수거 해줘야 할 개수

매번 while문 안에서 cap 만큼 빼주는 이유 : 해당 (i+1) 번째에서 트럭이 들려서 처리 가능한 최대 용량인 cap만큼 빼준거다.

빼줬더니 음수 : 현 상태에서 배달 수거에 필요한 용량 << cap이 더 크다는 뜻 (즉, 더 멀리 있는 집에서 배달/수거할 때 트럭 cap에 여유 있어서 지금 위치의 배달/수거는 미리 처리가 됐다는 뜻이다.)

빼줬더니 양수 : 현 상태에서 배달 수거에 필요한 용량 >> cap보다 크다는 뜻 (즉, 다 처리 못해서 물류 들렸다가 트럭이 다시 현 위치까지 와서 처리해줘야 한다는 거다. 따라서 현 위치까지 왕복거리 누적한다. )

실제로 처리된 집 출력

💚 제출 코드

1) 집 역순 순회하면서, d_cap과 c_cap에 현재 (i+1)번째 집에서 배달/수거할 값 누적 세팅

2) 코드에서 while 루프가 양수인 경우에만 실행되는 것은 현재 집에서 아직 처리되지 않은 택배가 남아있을 때를 의미

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int d_cap = 0; // 특정 지점에서 배달 해줘야 할 개수
        int p_cap = 0; // 특정 지점에서 수거 해줘야 할 개수
        
        for(int i=n-1; i>=0; i--){ // 역순 탐색 -> 가장 먼 집 부터 배달 및 수거 필요한지 확인한다.
            d_cap += deliveries[i]; // i+1 번째 집에 배달 해줘야 하는 개수를 더한다.
            p_cap += pickups[i]; // i+1 번째 집에서 수거 해줘야 하는 개수를 더한다.
            
            // 현재 탐색중인 집 (i+1 번째 집) 에 배달 및 수거가 필요하다면 (d_cap, p_cap 중 하나라도 0보다 크다)
            // 트럭이 여기(i+1 번째 집) 에 와야 한다.
            while(d_cap > 0 || p_cap > 0) {
                // 둘 중 하나라도 0보다 크다면 
                // -> i+1 번째 집에 아직 처리해야 할 배달 or 수거 항목이 있다는 뜻
                // -> i+1 번째 집까지 트럭이 와야 한다.
                answer += (i+1) * 2; // 트럭이 i+1 번째 집까지 왔으니까 거리 더해줌
            
                // i+1 번째 집까지 트럭이 왔으니, 트럭의 용량(cap) 만큼 배달 및 수거를 해줄 수 있다.
                d_cap -= cap;
                p_cap -= cap;
                
                // d_cap 과 p_cap 에서 cap 만큼 빼준 이유 : 트럭이 최대 cap 만큼 처리해줄 수 있기 때문
                //-> 현재 여기까지 트럭이 들려서 처리할 수 있는 최대 용량이 cap만큼이므로 각각 cap을 빼준거다.
                // if (d_cap, p_cap 에서 cap 을 뺐더니 음수)
                    // 배달 및 수거 필요한 용량보다 cap 이 더 크다는 뜻 
                    // 현재 지점 이전 집에 배달 및 수거 해 줄 여유가 있었다. 그래서 트럭이 또 올 필요는 없다.
                // if (d_cap, p_cap 에서 cap 을 뺐더니 양수)
                    // 배달 및 수거 필요한 용량보다 cap 이 더 작다는 뜻
                    // 현재 지점에 배달 및 수거가 더 필요하다. -> 트럭이 한번 더 와야한다.    
            }
            
            // d_cap, p_cap <= 0
            // 현재 지점 (i+1 번째 집) 의 배달 및 수거 처리가 이미 됐다. (더 먼 집에 트럭이 왔다갔다 하면서 이미 처리 했다.)
        }
        
        return answer;
    }
}