알고리즘/프로그래머스 Level2

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

류창 2023. 1. 7. 00:20
반응형

 

문제분석:

카카오 문제 Level2다.   다른 레벨 2와 비교해보면 격이다른 난이도를 돋보인다.

 

문제 요건: 트럭이 최소거리로 배달과 수거를 완료하는 거리를 구해주세요.

 

 

일단 어떻게 접근을 할까부터 생각해봤다.

 

곰곰히 규칙과 사례를 보니, 제일 먼 거리부터 배달과 수거행위를 한다.  

 

이거에 착안해서 로직을 시작했다.

 

 

d는  배달을 하러갈 지점,  p는 픽업을 하러갈 지점이다.

 

최초로 배달하러갈 지점과 픽업하러갈 지점을 구하고 간다.  

반드시, 마지막집에 물건이 있을 보장이없기때문이다.

 

 

이제부터 조금 긴 while문이 시작된다.  

 

종료조건과  거리계산을 설정했다.

 

종료조건은 배달과 픽업이 모두 완료댈때,  거리계산은 배달지점과 픽업지점중 높은값을 기준 *2한다.

 

그 이유는, 픽업이 높으면 픽업까지 배달이 높으면 배달까지 트럭이 이동할수밖에 없기때문이다.

 

배달하기 로직이다.

 

조건 1. 탈출로직

 

조건2. 배달하여 갯수를 뺍니다.

 

조건3.  간혹, 배달하는지점이 배달건수0인 지점에 멈추는 오류를 잡는 로직이다.

 

배달 로직과 동일하다.

 

이 부분을 메소드로 빼와서 더 간축시킬수 있을것같다.

문제풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import java.util.*;
class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        
        int d=0;
        int p=0;
        
        int size=cap;
        
        for(int i=n-1;i>=0;i--){
            if(deliveries[i]!=0){
                d=i+1;
                break;
            }
        }
        
         for(int i=n-1;i>=0;i--){
            if(pickups[i]!=0){
                p=i+1;
                break;
            }
        }
        
        while(true){  
            // 종료조건
            if(d==0&&p==0){
                break;
            }       
            //거리 계산
            answer+=(Math.max(d,p))*2;
               
            //배달하기
            while(true){
                if(d==0||cap==0&&deliveries[d-1]!=0){
                    break;
                }          
                if(cap>=deliveries[d-1]){
                    cap-=deliveries[d-1];
                    deliveries[d-1]=0;
                    d--;
                }
                else{
                    deliveries[d-1]-=cap;
                    cap=0;
                }             
                if(d==0){
                    break;
                }
                
                if(cap==0&&deliveries[d-1]==0){
                    d--;
                }
            }
            
            cap=size;
            
            //픽업하기
            while(true){
                if(p==0||cap==0&&pickups[p-1]!=0){
                    break;
                }
                
                if(cap>=pickups[p-1]){
                    cap-=pickups[p-1];
                    pickups[p-1]=0;
                    p--;
                }
                else{
                    pickups[p-1]-=cap;
                    cap=0;
                }
                
                if(p==0){
                    break;
                }
                
                if(cap==0&&pickups[p-1]==0){
                    p--;
                }
                      
            }
            
            cap=size;
        }
       
        
        
        return answer;
    }
}
cs
반응형