[프로그래머스] 2023 Kakao Blind Recuiment 택배 배달 수거하기

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

프로그래머스

📄 문제개요

• 배달해야할 택배와, 수거해야할 재활용 박스가 각 집에 주어졌을때, 트럭이 Cap크기만큼 박스를 트럭에 실을 수 있고, 트럭이 택배를 전달하고, 재활용 박스를 수거하는 최단경로를 구하시오.

🤔 문제분석

• 택배는 항상 Cap 크기만큼 전달한다.
• 재활용박스는 항상 Cap크기만큼 수거한다.
• 택배는 항상 맨 끝에있는 재활용박스를 거두어야할 집 혹은 배달해야할 집으로 이동해야한다.
• 스택 자료구조를 활용하여 문제를 해결 할 수 있다.
• 트럭은 항상 가장 멀리 있는 집부터 방문해야한다.

📝 의사코드

• 재활용박스의 후보군과, 배달해야할 택배의 후보군들을 스택 자료구조화 한다. ( 가장 멀리 있는 집부터 방문해야하기 때문 )

1. 택배가 이동해야할 거리를 구한다.
   • 재활용박스를 거두어야할 집과 배달해야할 집 중 가장 멀리있는 집이 트럭이 이동해야하는 거리이다.
2. 재활용박스와 택배박스를 스택에서 Cap 회 만큼 꺼낸다.
   • 트럭이 한번 이동할때, 재활용 박스와 택배박스는 항상 Cap 크기만큼 옮길 수 있다.
   • 따라서 Cap 만큼 재활용박스와 택배박스를 스택에서 꺼낸다.
3. 이동거리를 업데이트 한다 ( 집의 위치 * 2 )
4. 재활용 박스와 택배박스가 모두 스택에서 사라질때까지 1~3번을 반복한다.

💻 코드

def solution(cap, n, deliveries, pickups):
    s_deliveries = []
    s_pickups = []
    for i in range(n):
        if deliveries[i]:
            for _ in range(deliveries[i]):
                s_deliveries.append(i+1)
                
        if pickups[i]:
            for _ in range(pickups[i]):
                s_pickups.append(i+1)
    
    answer = 0
    while s_deliveries or s_pickups:
        # 재활용상자와 배달상자가 모두 있는경우
        move_pos = 0
        if s_deliveries and s_pickups:
            move_pos = max(s_deliveries[-1], s_pickups[-1])
        # 배달상자만 있는경우
        elif s_deliveries:
            move_pos = s_deliveries[-1]
        # 픽업상자만 있는경우
        else:
            move_pos = s_pickups[-1]
            
        for _ in range(cap):
            if s_deliveries:
                s_deliveries.pop()
                
            if s_pickups:
                s_pickups.pop()
            
        #트럭이 이동해야할 거리
        answer += move_pos * 2
        
    return answer

🎯 피드백 및 개선사항

• 이 문제는 가장 최고의 선택을 계속 반복하면서 최적해를 구해나가는 그리디 접근 방식을 생각해내야하는게 핵심 포인트이다.
• 가장 베스트한 조건을 반복하여 최대거리를 구한다.

❓다른사람은 어떻게 풀었을까?

• 누적합으로 문제를 해결 한 분이 있다… (대박…)

def solution(cap, n, deliveries, pickups):
    answer = 0
    # 역순으로 누적합
    for i in range(n-2, -1, -1):
        deliveries[i] += deliveries[i+1]
        pickups[i] += pickups[i+1]
    k = 0
    for i in range(n-1, -1, -1):
        while deliveries[i] > cap*k or pickups[i] > cap*k:
            answer += (i+1)*2
            k += 1
    return answer

• 스택 자료구조 없이 문제를 해결 하신분… 너무나 대단하다고 생각합니다.. ㅠㅠ

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

    d = 0
    p = 0

    for i in range(n-1, -1, -1):

        cnt = 0

        d -= deliveries[i]
        p -= pickups[i]

        while d < 0 or p < 0:
            d += cap
            p += cap
            cnt += 1

        answer += (i + 1) * 2 * cnt

    return answer