📜 문제
풀이
스택
deliveries와 pickups를 스택으로 사용해서 풀었다. 배달과 수거는 같이 이뤄지는 것 같지만 사실은 개별적으로 이뤄지는 거나 다름 없다. 배달해야 할 것과 수거해야 할 것 중 가장 멀리 있는 걸 기준으로 두면 된다.
만약 배달해야 할 택배가 7의 거리에 있다면 그 이전에 있는 수거해야 할 것들은 배달한 후에 무조건 수거해올 수 있다. 반대로 수거해야 할 것이 9에 있고 배달해야 할 게 5에 있다면 배달이 끝나고 수거를 하러 또 이동하면 된다. 중요한 건 배달이든 수거든 둘 중 가장 먼 것의 길이를 구하면 된다는 것.
배달해야 할 것과 수거해야 할 것이 있는 경우(0이 아닌 경우)를 찾고, 없다면 pop()을 통해서 스택에서 제거해나가면서 문제를 풀었다. 시간은 생각보다 오래 걸림.
def solution(cap, n, deliveries, pickups):
answer = 0
while deliveries or pickups:
while deliveries and deliveries[-1] == 0:
deliveries.pop()
while pickups and pickups[-1] == 0:
pickups.pop()
answer += max(len(deliveries)*2, len(pickups)*2)
limit = cap
while deliveries and limit:
if deliveries[-1] >= limit:
deliveries[-1] -= limit
break
limit -= deliveries.pop()
limit = 0
while pickups and limit < cap:
if pickups[-1] >= cap-limit:
pickups[-1] -= cap-limit
break
limit += pickups.pop()
return answer
16번 무슨일;
그리디
로 푸는 방법이 있었다.
위에서 언급했듯이 이 문제는 배달과 수거가 복잡하게 얽혀 있는 것처럼 보이는 게 함정이다. 실제로는 걍 배달이 젤 멀리 있으면 배달하고 그 이전에 있는 것들 수거하면서 되돌아오면 되고, 수거가 멀리 있으면 이전에 있는 거 배달하고 제일 멀리있는 걸 수거해서 되돌아오면 된다. 어찌됐든 둘 중 제일 멀리있는 곳까지의 거리만 더해주면 되는 것.
여기서 deliver는 현재 배달해야 할 개수이다. pick은 수거. 값이 0이면 배달 or 수거해야 할 게 없다는 뜻이고, 음수면 해야 할 게 있다는 뜻이다. 배달이든 수거든 해야 할 게 있다면 그 위치까지는 무조건 이동해야 하기 때문에 answer에 위치 * 2(왔다갔다해야 하니까)를 해준다. 그리고 배달과 수거를 했다는 표시를 하기 위해서 cap을 더해준다.
deliver와 pick의 값이 cap을 더해주면서 양수가 된다면, 이 값은 배달 or 수거해야 할 게 있다는 음수의 뜻과 반대로 이 만큼 더 배달 or 수거할 수 있다는 뜻이다. 값이 계속 양수로 남아 있다면 사실상 이 위치에서는 배달 or 수거를 해야 할 게 없으니 지나가도 된다.
중요한 건 두 개의 값이 음수가 된다면 그 위치는 지나칠 수 없고 반드시 배달과 수거가 이루어져야 한다는 것. 실생활에서는 보통 양수로 표시되는 걸 여기서는 음수로 바꿔서 조금 헷갈릴 수 있는 것 같다.
def solution(cap, n, deliveries, pickups):
answer = 0
deliver = pick = 0
for distance in range(n-1, -1, -1):
deliver -= deliveries[distance]
pick -= pickups[distance]
while deliver < 0 or pick < 0:
deliver += cap
pick += cap
answer += (distance+1)*2
return answer
스택 쓰는 것보다 1/5 정도 줄었다
