🐒 문제
https://programmers.co.kr/learn/courses/30/lessons/42583
✍ 나의 풀이
from collections import deque
def solution(bridge_length, weight, truck_weights):
answer = 1
q = deque(truck_weights)
onboard = deque([0 for _ in range(bridge_length)])
onweight = q.popleft()
onboard.append(onweight)
onboard.popleft()
while onweight:
if onboard.popleft():
onweight = sum(onboard)
if q:
if onweight + q[0] <= weight:
onboard.append(q.popleft())
onweight = sum(onboard)
else:
onboard.append(0)
answer += 1
return answer정확성 테스트
테스트 1 〉 통과 (0.40ms, 10.3MB)
테스트 2 〉 통과 (6.38ms, 10.4MB)
테스트 3 〉 통과 (0.02ms, 10.3MB)
테스트 4 〉 통과 (11.39ms, 10.3MB)
테스트 5 〉 통과 (88.36ms, 10.4MB)
테스트 6 〉 통과 (31.94ms, 10.2MB)
테스트 7 〉 통과 (0.32ms, 10.2MB)
테스트 8 〉 통과 (0.08ms, 10.3MB)
테스트 9 〉 통과 (1.89ms, 10.2MB)
테스트 10 〉 통과 (0.09ms, 10.2MB)
테스트 11 〉 통과 (0.01ms, 10.2MB)
테스트 12 〉 통과 (0.16ms, 10.2MB)
테스트 13 〉 통과 (0.55ms, 10.2MB)
테스트 14 〉 통과 (0.02ms, 10.2MB)
채점 결과
정확성: 100.0
합계: 100.0 / 100.0스택 & 큐 카테고리의 문제를 풀었다.
문제를 이해하는데 시간이 많이 걸렸다.
처음 제출한 코드는 5번 테스트케이스만 시간초과가 발생해서 수정하였다.
🧠 문제 이해
모든 트럭이 순서대로 다리를 통과해야한다.
다리는 bridge_length 의 길이를 가지며, weight의 하중을 견딘다.
따라서 다리위의 트럭들의 무게의 합은 weight보다 같거나 작아야한다.
트럭들의 무게는 truck_weights 리스트에 저장되어있다.
트럭이 한번 앞으로 이동할때 1초가 걸릴때 모든트럭이 통과하는 최단시간을 리턴해야한다.
나는 큐 자료구조를 이용해 bridge_length만큼의 길이를 가지는 다리를 구현했다.
처음 코드(시간초과)
from collections import deque
def solution(bridge_length, weight, truck_weights):
answer = 0
q = deque(truck_weights)
onboard = deque([0 for _ in range(bridge_length)])
while q or sum(onboard) != 0: # 다리 건너기를 기다리는 트럭이 없거나, 다리에 올라간 트럭이 없으면 종료하는 while문
onboard.popleft()
if q:
if sum(onboard) + q[0] <= weight:
onboard.append(q.popleft())
else:
onboard.append(0)
else:
onboard.append(0)
answer += 1
return answer정확성 테스트
테스트 1 〉 통과 (24.41ms, 10.2MB)
테스트 2 〉 통과 (1950.99ms, 10.3MB)
테스트 3 〉 통과 (0.04ms, 10.2MB)
테스트 4 〉 통과 (372.07ms, 10.4MB)
테스트 5 〉 실패 (시간 초과)
테스트 6 〉 통과 (1803.24ms, 10.4MB)
테스트 7 〉 통과 (8.24ms, 10.2MB)
테스트 8 〉 통과 (0.24ms, 10.1MB)
테스트 9 〉 통과 (5.07ms, 10.2MB)
테스트 10 〉 통과 (0.50ms, 10.3MB)
테스트 11 〉 통과 (0.01ms, 10.3MB)
테스트 12 〉 통과 (0.25ms, 10.3MB)
테스트 13 〉 통과 (1.87ms, 10.2MB)
테스트 14 〉 통과 (0.09ms, 10.1MB)
채점 결과
정확성: 92.9
합계: 92.9 / 100.0질문게시판에서 나처럼 5번 테스트케이스만 시간초과가 발생하는 경우를 볼 수 있었다. https://programmers.co.kr/questions/26172
답변에는 sum()함수는 O(n)의 시간 복잡도를 가지기때문에 조건을 부여하여 함수사용을 줄일 것을 권장하고있다.
두번째 코드 (성공)
from collections import deque
def solution(bridge_length, weight, truck_weights):
answer = 1
q = deque(truck_weights)
onboard = deque([0 for _ in range(bridge_length)])
# 시간이 1초일때 트럭 한대는 무조건 다리위로 올라간다.
onweight = q.popleft()
onboard.append(onweight)
onboard.popleft()
while onweight: # 다리에 올라간 트럭이 있으면
if onboard.popleft(): #다리 맨 왼쪽에 트럭이 나가면
onweight = sum(onboard) # 다리 위 트럭들 무게 업데이트
if q: # 다리 건너기를 기다리는 트럭이 있다면
if onweight + q[0] <= weight: # 다리 위 트럭들의 무게와 다음 올라올 트럭의 무게가 최대하중보다 작거나 같으면
onboard.append(q.popleft()) #다리위에 다음 올라올 트럭을 올린다.
onweight = sum(onboard) # 다리 위 트럭들 무게 업데이트
else: # 트럭이 못올라가면 0을 붙여서 다리위 트럭들 앞으로 이동
onboard.append(0)
answer += 1
return answer리팩토링
나는 다리 건너길 기다리는 트럭들 리스트의 왼쪽부터 순서대로 건너야하니
q = deque(truck_weight)을 통해
truck_weight 리스트를 q로 대신하여 popleft()를 사용할 수 있게했다.
그러나 truck_weight 리스트를 그대로 사용하여도 크게 시간차이가 나지않았다.
아마도 큐 는 선입선출에 특화된 자료구조인데 "선입"도 없고 순서도 이미 정해져있고 나가기만 하니 이런 결과가 나온 것같다.
from collections import deque
def solution(bridge_length, weight, truck_weights):
answer = 1
onboard = deque([0]*bridge_length) # << 조금 더 짧게 표현
# q = deque(truck_weights) 없앰
onweight = truck_weights.pop(0)
onboard.append(onweight)
onboard.popleft()
while onweight:
if onboard.popleft():
onweight = sum(onboard)
if truck_weights:
if onweight + truck_weights[0] <= weight:
onboard.append(truck_weights.pop(0))
onweight = sum(onboard)
else:
onboard.append(0)
answer += 1
return answer