[Python - 프로그래머스] 2023 KAKAO BLIND RECRUITMENT > 택배 배달과 수거하기

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

프로그래머스

 

---

Solution

내가 했던 풀이는 다음과 같다. (아래 풀이는 테스트 15번부터 시간초과가 뜬다. 그 외 테스트 케이스는 통과이다.)

 

import numpy as np
import math
import itertools
 
def fun(deliveries, cap) :
    an = list()
    cs = np.array(deliveries[::-1]).cumsum()[::-1]
    while len(np.where(cs>0)[0]) > 0 :
        idx = max(np.where(cs>0)[0])
        m = math.ceil(cs[idx]/cap)
        an.append([idx+1]*m)
        cs = cs - cap*m
    return list(itertools.chain(*an))
 
def solution(cap, n, deliveries, pickups):
    de = fun(deliveries, cap)
    pi = fun(pickups, cap)
    
#     print(de)
#     print(pi)
    
    if len(de) == len(pi) :
        answer = [i if i >= j else j for i, j in zip(de, pi)]
        answer = sum(answer)
    elif len(de) > len(pi) :
        answer = sum([i if i >= j else j for i, j in zip(de[:len(pi)], pi)]) + sum(de[len(pi):])
    else :
        answer = sum([i if i >= j else j for i, j in zip(de, pi[:len(de)])]) + sum(pi[len(de):])
        
    return int(answer)*2
 

 

deliveries와 pickups를 따로 구하고, 둘 중에 distance가 더 긴 걸로 최종 answer를 구했다.

근데 이 방법은 시간초과가 떠서 결국 다른 사람의 도움으로 풀었다.

 

---

다른 사람의 풀이

 

이 문제는 탐욕법(Greedy Algorithm)으로 풀어야 한다.

 

def solution(cap, n, deliveries, pickups):
    give = 0; take = 0;
    answer = 0
    for i in range(n-1,-1,-1) :
        cnt = 0
        while ((give < deliveries[i]) | (take < pickups[i])) :
            cnt += 1
            give += cap
            take += cap
        give -= deliveries[i]
        take -= pickups[i]
        answer = answer + (i+1)*cnt*2
    return answer

 

give는 줄 수있는 개수, take는 받아 올 수 있는 개수이다.

cnt는 주기위해 or 받기 위해 가야 하는 횟수이다.

 

for 문으로 맨 뒤에서부터 주고 받으며 distance를 더해간다.

 

give랑 take를 따로 생각하고 풀어도된다는게 신기하다..