프로그래머스 - 택배 배달과 수거하기 (Python)

lv. 2 단계의 코딩 테스트 연습 문제 중 '택배 배달과 수거하기'에 대한 풀이를 설명하고 있습니다.

 

프로그래머스 - 택배 배달과 수거하기 (Python)

 

코딩 테스트 연습 문제 풀이

 

1. 원리

2. 코드

위의 목차를 클릭하면 해당 글로 자동 이동 합니다.

 

원리

• 가장 끝 집부터 방문해야 되는 것을 이미 눈치챘기 때문에 뒤에서 부터 탐색하면서 수거할 것이 있거나 배달해야 할 것이 있으면 해당 집까지의 거리는 무조건 왔다 가야 된다는 것을 떠올렸다.
• 그러면 내가 그 집까지 왔다갔다 하면서 cap 만큼의 택배를 배달하고 수거할 수 있으므로, i번째 칸까지 온 상태에서 i-1 ~ 0 칸까지 다시 탐색을 하면서 cap 만큼의 택배들 그리고 수거 상자들의 수를 갱신했다.
• 하지만 이렇게 구현하면 4가지의 테스트 케이스를 통과하지 못한다.
• 그 이유는 100000개의 집을 탐색할 때, 첫 번째 집과 마지막 집에 택배 물품이 있는 경우가 문제가 된다.
  • 마지막 집까지 내가 왔으니까 그 앞 집에서 배달과 수거가 일어난 만큼 값을 갱신해주어야 하는데, 첫 번째 집을 제외하면 모든 집이 값이 없으므로, 결국 첫 번째 집까지 탐색을 이어나간다.
  • 이런 일이 자주 반복되면 결국 100000 X 100000 의 시간 복잡도를 갖는다.

1	2	3	4	5	6
1	1	0	0	1	1
0	0	1	1	0	0

• 위의 예시가 주어지고 cap가 2라고 해보자.
  • 일단 6번 집까지는 무조건 와야한다.
  • 그러면 6번 집까지 오는 길에 1개를 배달하고 2개를 수거할 수 있으므로, 6번 집부터 거슬러 내려오면서  1개는 배달한 것으로, 2개는 수거한 것으로 갱신한다. 그러면 아래와 같이 갱신된다.

1	2	3	4	5	6
1	1	0	0	0	0
0	0	0	0	0	0

• 그러면 우리는 뒤에서부터 내려오면서 다음 집으로 탐색을 넘어간다.
• 현재 수거할 것이나 배달할 것이 남아있는 집이 2번 집이므로, 다음 탐색은 2번에서 일어나게 된다.
• 앞서 말했듯이, 이 방식으로 풀면 조건문도 많이 발생하지만 최악의 경우 시간 복잡도를 지키지 못한다.

 

• 따라서 다른 분의 풀이를 참고했다.
  • 아이디어는 간단한데, 만약 i 번째 집까지 와야되는 상황에서 굳이 앞 집들을 탐색하면서 일일히 값을 갱신하지말고 내가 얼마나 배달했는지, 혹은 수거했는지를 음수의 형태로 가지고 있는 것이다.
  • 그러면 i 번째 집에서 4개 중에 2개를 배달했다면 -2만큼의 배달 여유를 가질 수 있으니 그 앞집들을 탐색할 때, 2개 이상 배달해야 하는 경우를 마주치면 해당 집까지 와야되는 것을 의미한다.
• 앞선 상황과 똑같은 상황을 가정해보자

1	2	3	4	5	6
1	1	0	0	1	1
0	0	1	1	0	0

• 우리는 6번 집에 배달할 것이 1개 존재하므로, 마찬가지로 6번 집까지 오는 길에 1개를 배달하고 2개를 더 수거할 수 있다.
• 따라서 willDelivery = -1 이고, willPickup = 2이다.
• 그리고 6번 집까지는 한번 왔으니 6 X 2 = 12의 거리가 정답에 추가된다.

1	2	3	4	5	6
1	1	0	0	1	0
0	0	1	1	0	0

• 6번 집에 더 이상 볼일이 없으므로, 5번 집으로 내려간다.
• 5번 집에서 배달할 것이 하나 있지만, 현재 willDelivery를 확인해보니 1개는 6번을 찍턴할 때 배달을 했다고 기록되어 있다. 따라서 5번 집은 올 필요가 없다.
• 그러므로 willDelivery에 5번 집의 배달 수량을 더해준다.
• 그러면 willDelivery = 0으로 다음 번에 배달이 필요한 집을 만난다면 해당 집으로 배달을 위해서는 무조건 그 집을 들려야 한다는 것을 의미한다.

1	2	3	4	5	6
1	1	0	0	1	0
0	0	1	1	0	0

• 4번 집도 마찬가지로 수거를 1개 해야하지만 6번 집을 방문할 때, 이미 2개까지는 수거한 것으로 되어있기 때문에 4번 집은 패스한다.
• willPickup에 4번 집의 수거 수량을 더해준다.
• 그러면 willPickup = 1이 된다.
• 마찬가지로 3번 집에서도 아직 willPickup 수량이 여유롭기 때문에 6번 집을 들리는 동안 수거가 가능한 것이다.
• 따라서 willPickup에 3번 집의 수거 수량을 더해 willPickup = 0 이 된다.
• 이 경우, 다음 번에 수거가 필요한 집을 만난다면 해당 집의 수거를 위해서는 무조건 그 집을 한 번 들려야 한다.

 

• 이런식으로 뒤 부분부터 탐색을 시도하면 된다.
• 만약 특정 집의 배달 수량이나 수거 수량이 cap 이상만큼 있는 경우, 모두 수거될 때까지 반복한다.
• 전체 코드는 아래와 같다.
• 부분 부분 코드를 설명하지 않는 이유는 코드가 굉장히 간단하기 때문이다.

코드

def solution(cap, n, deliveries, pickups):
    answer = 0

    willDelivery = 0
    willPickup = 0
    for i in range(len(deliveries)-1, -1, -1):
        willDelivery += deliveries[i]
        willPickup += pickups[i]

        while willDelivery > 0 or willPickup > 0:
            answer += ((i + 1) * 2)
            willDelivery -= cap
            willPickup -= cap
    return answer

 

내 방식대로 풀어서 마무리를 하고 싶었는데, 가장 처음에 언급한 방식으로는 아무리 탈출 조건을 잘 세운다한들 통과하기는 쉽지 않아서 아쉽다. 아쉬운 이유는 코드의 형태가 내 아이디어와 유사해서인데, 굳이 값을 일일히 갱신하는 것에 집중하지 않았으면 쉽게 풀 수 있었을 것 같다.