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

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

프로그래머스

 

처음에는 단순하게 앞에서 부터 탐색하는 방향으로 구현했는데 시간초과가 났다.

최적화하는 방향을 생각해보니깐 뒤에서 부터 하면 여러 조건문들이 사라진다.

 

뒤에서 시작한다고 그리디 문제인가?? 뒤에서부터 탐색했을 때는 시간초과가 안났다.

아무튼 글 쓰기 전에 본 카카오 풀이에서는 그리디 문제라고 했으니까 그리디이다.

 

1번 코드

deliveries와 pickups의 합을 구해서 total에 저장하고

total을 각 배열을 탐색하면서 -1씩 깍아갈 예정이라서 while문의 조건으로 뒀다.

 

while문을 사용하니 index를 따로 선언하고 이를 통해 탐색할 것이고 각 배열별로 index를 둬서

한 사이클(택배가 물류창고에서 한번 출발하고 도착하는 사이클)이 동시에 이뤄지지만 탐색하는 곳은 각각 다르다.

 

remain을 각 배열별로 둬서 현재 얼마나 수거할 수 있고 배달할 물건을 얼마나 실고 있는지를 저장한다.

while문을 통해 반복하며 각 remain이 0이 되면 total과 각 집에 해당하는 남은 수거량이나 배달량을 -1씩 깍는 것을 멈추도록 한다.

 

각 remain이 0이 된다면 위 사이클을 멈추고 while문을 탈출한다.

 

해당 집에 연산할 것이 없다면 index를 -1씩하며 앞 집으로 이동한다.

 

여기까지 했으면 될 것 같지만?? 사실 안된다 ㅋㅋ

remain이 0이더라도 배달하거나 수거할 물건이 해당 집에 없다면 index를 계속 내려야한다.

 

1. total 계산, d_index, p_index를 가장 끝 집으로 설정

2. total이 있는 동안 반복될 while문 시작, while문의 시작으로 돌아가면 한 사이클의 시작인 것이다!

3. 배달, 수거 가능한 양을 나타낼 d_remain, p_remain을 cap으로 초기화

3-1. d_index와 p_index를 비교하고 가장 멀리 있는 index에 다시 가야하니까 answer에 +1해서 더해주기 (왕복이니까 * 2)

4. 각 index가 유효하고 배달, 수거 가능한 remain이 있다는 조건이 있는 while문 시작

4-1. 해당 집에 배달, 수거를 해야하만 한다면 while문 시작. 조건은 작업량이 남아있을 때까지

4-1-1. 만약 remain이 0이라면 작업 while을 break로 종료

4-1-2. 아니라면 total과 작업할 집의 작업량, remain을 -1씩 해가기

4-2. 작업 while이 break가 아니게 탈출했다면 작업이 끝난 것이니 -1

5. remain이 0이더라도 작업량이 남은 집이 아니라면 굳이 다시 올 필요가 없으니 index를 -1씩 해준다

 

첫 코드

def solution(cap, n, deliveries, pickups):
    answer = 0
    total = sum(deliveries) + sum(pickups)
    
    d_index = n - 1
    p_index = n - 1
    
    while total > 0:
        d_remain = cap
        p_remain = cap
        
        answer += (max(d_index,p_index) + 1) * 2
        while d_index >= 0 and d_remain > 0:
            while deliveries[d_index]:
                if d_remain == 0:
                    break
                deliveries[d_index] -= 1
                total -= 1
                d_remain -= 1
            else:
                d_index -= 1
        while d_index >= 0 and not deliveries[d_index]:
            d_index -= 1
        
        while p_index >= 0 and p_remain > 0:
            while pickups[p_index]:
                if p_remain == 0:
                    break
                pickups[p_index] -= 1
                total -= 1
                p_remain -= 1
            else:
                p_index -= 1
        
        while p_index >= 0 and not pickups[p_index]:

            p_index -= 1
            
    return answer

결과

사실 -1씩 해가는 것이 오래걸릴 줄 알았는데 통과해서 최적화를 위해서

-1씩 하는 것을 작업량 전체로 빼서 remain이 0 초과이면 index를 빼고

remain이 0 이하라면 total과 작업 중인 집을 이하인 만큼 다시 더해주고 한 사이클을 종료시키는 방식

 

두번째 코드

def solution(cap, n, deliveries, pickups):
    answer = 0
    total = sum(deliveries) + sum(pickups)
    
    d_index = n - 1
    p_index = n - 1
    
    while total > 0:
        d_remain = cap
        p_remain = cap
        
        answer += (max(d_index,p_index) + 1) * 2
        while d_index >= 0 and d_remain > 0:
            total -= deliveries[d_index]
            d_remain -= deliveries[d_index]
            deliveries[d_index] = 0
                
            if d_remain <= 0:
                deliveries[d_index] += -d_remain
                total += -d_remain
                d_remain = 0
                break
            else:
                d_index -= 1
                
        while d_index >= 0 and not deliveries[d_index]:
            d_index -= 1
        
        while p_index >= 0 and p_remain > 0:
            total -= pickups[p_index]
            p_remain -= pickups[p_index]
            pickups[p_index] = 0
                
            if p_remain <= 0:
                pickups[p_index] += -p_remain
                total += -p_remain
                p_remain = 0
                break
            else:
                p_index -= 1
        
        while p_index >= 0 and not pickups[p_index]:
            p_index -= 1
            
    return answer

결과

16번이 왜 더 오래걸리는지 모르겠다 ㅠㅠ

아무튼 더 최적화할 수 있는 방향을 생각해봤는데 이런 복잡한 조건문 필요없이?? 해주면 될 것 같아서

 

1. 처음 작업 시작 인덱스를 구하고 answer에 더해주고

2. 그 인덱스부터 뒤에서 시작해서 앞으로 오고

3. 작업량을 remain에 빼주고 remain이 0보다 작아지면 다시 와야하는 것이니까 cap만큼 다시 더해주면서 answer에도 더해주면

 

결국 로직은 같게 된다..

 

세번째 코드

def solution(cap, n, deliveries, pickups):
    answer = 0
    
    d_remain = cap
    p_remain = cap
    
    start = 0
    for i in range(n-1,-1,-1):
        if deliveries[i] or pickups[i]:
            start = i
            answer += (start + 1) * 2
            break
            
    for i in range(start, -1, -1):
        d_remain -= deliveries[i]
        p_remain -= pickups[i]
        
        while d_remain < 0 or p_remain < 0:
            d_remain += cap
            p_remain += cap
            answer += (i + 1) * 2
        
    return answer

결과

예~