2023 KAKAO BLIND RECRUITMENT - 택배 배달과 수거하기

2023 KAKAO BLIND RECRUITMENT - 택배 배달과 수거하기

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

cap=4 일 때, 최소 거리로 배달을 완료하는 방법은
배달 갈 때 가장 먼 집부터 4개의 택배를 배달
돌아올 때도 가장 먼 집부터 4개의 바구니를 회수하는 것이다. 

배달시, 회수시 각각 터닝 포인트 후보들을 뽑은 뒤
포인트의 쌍을 만들어 가장 먼 곳을 터닝  포인트로 잡으면 된다. 

def solution(cap, n, deliveries, pickups):
    def get_points(array):
        points = []
        box, index = 0, n - 1
        while index > -1:
            if array[index] == 0:
                index -= 1
                continue
            if box == 0:
                points.append(index)
            capacity = cap - box
            if array[index] < capacity:
                box += array[index]
                index -= 1
            elif array[index] == capacity:
                box = 0
                index -= 1
            else:
                array[index] -= capacity
                box = 0
        return points[::-1]

    answer = 0
    d_points, p_points = get_points(deliveries), get_points(pickups)
    while d_points or p_points:
        answer += max(d_points.pop() if d_points else 0, p_points.pop() if p_points else 0) + 1
    return answer * 2

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.00ms, 10.1MB)
테스트 3 〉	통과 (0.02ms, 10.2MB)
테스트 4 〉	통과 (0.02ms, 10.1MB)
테스트 5 〉	통과 (0.06ms, 10.4MB)
테스트 6 〉	통과 (0.03ms, 10.2MB)
테스트 7 〉	통과 (0.61ms, 10.2MB)
테스트 8 〉	통과 (1.52ms, 10.3MB)
테스트 9 〉	통과 (8.10ms, 10.5MB)
테스트 10 〉	통과 (5.00ms, 10.3MB)
테스트 11 〉	통과 (5.03ms, 10.3MB)
테스트 12 〉	통과 (3.37ms, 10.4MB)
테스트 13 〉	통과 (3.26ms, 10.1MB)
테스트 14 〉	통과 (1.57ms, 10.5MB)
테스트 15 〉	통과 (23.96ms, 11.8MB)
테스트 16 〉	통과 (1726.00ms, 69.6MB)
테스트 17 〉	통과 (139.91ms, 17.2MB)
테스트 18 〉	통과 (73.04ms, 15.6MB)
테스트 19 〉	통과 (57.17ms, 13.2MB)
테스트 20 〉	통과 (54.34ms, 13.9MB)

조금 더 깔끔하게 만든다면.. 

def solution(cap, n, deliveries, pickups):
    def get_points(array):
        points = []
        box, index = 0, n - 1
        while index > -1:
            if array[index] == 0:
                index -= 1
                continue
            if box == 0:
                points.append(index)
            capacity = cap - box
            if array[index] <= capacity:
                box += array[index]
                index -= 1
            else:
                array[index] -= capacity
                box = 0
        return points[::-1]

    answer = 0
    d_points, p_points = get_points(deliveries), get_points(pickups)
    while d_points or p_points:
        answer += max(d_points.pop() if d_points else 0, p_points.pop() if p_points else 0) + 1
    return answer * 2

테스트 1 〉	통과 (0.02ms, 10.2MB)
테스트 2 〉	통과 (0.01ms, 10.1MB)
테스트 3 〉	통과 (0.04ms, 10.3MB)
테스트 4 〉	통과 (0.04ms, 10.1MB)
테스트 5 〉	통과 (0.08ms, 10.2MB)
테스트 6 〉	통과 (0.03ms, 10.2MB)
테스트 7 〉	통과 (0.58ms, 10.4MB)
테스트 8 〉	통과 (3.74ms, 10.4MB)
테스트 9 〉	통과 (13.30ms, 10.5MB)
테스트 10 〉	통과 (10.35ms, 10.3MB)
테스트 11 〉	통과 (2.59ms, 10.3MB)
테스트 12 〉	통과 (2.07ms, 10.3MB)
테스트 13 〉	통과 (3.17ms, 10.2MB)
테스트 14 〉	통과 (3.27ms, 10.4MB)
테스트 15 〉	통과 (25.47ms, 11.7MB)
테스트 16 〉	통과 (1677.43ms, 69.6MB)
테스트 17 〉	통과 (183.93ms, 17.3MB)
테스트 18 〉	통과 (70.82ms, 15.6MB)
테스트 19 〉	통과 (55.63ms, 13.2MB)
테스트 20 〉	통과 (63.75ms, 14MB)

속도를 위해 뒤집지 않고...

deque를 사용할 수도 있지만,
iter를 사용하는 방법도 있다. 

def solution(cap, n, deliveries, pickups):
    def get_points(array):
        points = []  # turning points
        box, index = 0, n - 1
        while index > -1:
            if array[index] == 0:
                index -= 1
                continue
            if box == 0:
                points.append(index)
            capacity = cap - box
            if array[index] <= capacity:
                box += array[index]
                index -= 1
            else:
                array[index] -= capacity
                box = 0
        return iter(points), len(points)

    answer = 0
    (d_points, d_length), (p_points, p_length) = get_points(deliveries), get_points(pickups)
    for _ in range(max(d_length, p_length)):
        answer += max(next(d_points, 0), next(p_points, 0)) + 1
    return answer * 2

조금 더 줄여 본다면.. 

def solution(cap, n, deliveries, pickups):
    def get_points(array):
        points = []  # turning points
        box, index = 0, n - 1
        while index > -1:
            if array[index] == 0:
                index -= 1
                continue
            if box == 0:
                points.append(index)
            capacity = cap - box
            if array[index] <= capacity:
                box += array[index]
                index -= 1
            else:
                array[index] -= capacity
                box = 0
        return iter(points), len(points)

    (d_points, d_length), (p_points, p_length) = get_points(deliveries), get_points(pickups)
    return sum(max(next(d_points, 0), next(p_points, 0)) + 1 for _ in range(max(d_length, p_length))) * 2

테스트 1 〉	통과 (0.02ms, 10.3MB)
테스트 2 〉	통과 (0.01ms, 10.4MB)
테스트 3 〉	통과 (0.02ms, 10.2MB)
테스트 4 〉	통과 (0.03ms, 10.2MB)
테스트 5 〉	통과 (0.07ms, 10.2MB)
테스트 6 〉	통과 (0.03ms, 10.3MB)
테스트 7 〉	통과 (0.56ms, 10.3MB)
테스트 8 〉	통과 (2.65ms, 10.3MB)
테스트 9 〉	통과 (11.95ms, 10.5MB)
테스트 10 〉	통과 (9.05ms, 10.4MB)
테스트 11 〉	통과 (2.46ms, 10.3MB)
테스트 12 〉	통과 (2.19ms, 10.3MB)
테스트 13 〉	통과 (1.56ms, 10.3MB)
테스트 14 〉	통과 (1.55ms, 10.3MB)
테스트 15 〉	통과 (25.15ms, 11.8MB)
테스트 16 〉	통과 (1584.63ms, 52.6MB)
테스트 17 〉	통과 (159.17ms, 16.8MB)
테스트 18 〉	통과 (110.32ms, 16MB)
테스트 19 〉	통과 (45.79ms, 13.2MB)
테스트 20 〉	통과 (76.35ms, 14MB)