문제
https://school.programmers.co.kr/learn/courses/30/lessons/42583
풀이 1
https://github.com/nowChae/algorithm/blob/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/2/42583.%E2%80%85%EB%8B%A4%EB%A6%AC%EB%A5%BC%E2%80%85%EC%A7%80%EB%82%98%EB%8A%94%E2%80%85%ED%8A%B8%EB%9F%AD/%EB%8B%A4%EB%A6%AC%EB%A5%BC%E2%80%85%EC%A7%80%EB%82%98%EB%8A%94%E2%80%85%ED%8A%B8%EB%9F%AD.py
풀이 2
https://github.com/nowChae/algorithm/blob/master/programmers/programmers42583.py
전에 풀었던 문제를 다시 풀어보았다. 처음 이 문제를 봤을 때는 queue와 deque 라이브러리 등에 대한 지식이 확실하지 않았던 터라 풀이를 보고 난 후 풀었던 것 같은 데 이번에 stack, queue, dequeue에 대한 정리를 좀 해 본 후 다시 풀어보았다.
처음 sum을 사용해서 코드를 구현하니 제출했을 때 5번째 테스트 케이스에서 계속 시간 초과가 발생했다. sum 메소드 사용으로 인해 시간 초과가 되는 것인가 해서 sum을 사용하지 않고 새롭게 current_weight 라는 변수를 두고 다리 위의 무게를 구하도록 수정했다.
변수를 사용하니 sum을 통해 계속 전체 bridge의 합을 구할 필요가 사라져서 시간 초과 없이 성공적으로 완료되었다. while 문 안에 bridge_length 수 만큼의 sum을 계속 구하다 보니 시간적으로 효율적이지 못했던 것 같다.
< 풀이 코드 - 시간 초과 >
from collections import deque
def solution(bridge_length, weight, truck_weights):
bridge = deque(list([0]*(bridge_length)))
truck_weights = deque(truck_weights)
second = 0
while len(truck_weights):
if sum(bridge) + truck_weights[0] - bridge[0] <= weight:
bridge.append(truck_weights.popleft())
bridge.popleft()
second += 1
else:
bridge.append(0)
bridge.popleft()
second += 1
second += bridge_length
return second< 풀이 코드 - 수정 후 >
from collections import deque
def solution(bridge_length, weight, truck_weights):
bridge = deque([0]*(bridge_length))
truck_weights = deque(truck_weights)
second = 0
current_weight = 0
while len(truck_weights):
if current_weight + truck_weights[0] - bridge[0] <= weight:
current_weight += truck_weights[0]
bridge.append(truck_weights.popleft())
current_weight -= bridge.popleft()
second += 1
else:
bridge.append(0)
current_weight -= bridge.popleft()
second += 1
second += bridge_length
return second