[알고리즘 문제 풀이🙄] 백준 13335. 트럭 (silver 1)

📌 문제 요약

강 위의 다리를 n개의 트럭이 지나가려고 한다. 다리 위에는 w대의 트럭만이 동시에 올라갈 수 있다고 할 때, 모든 트럭들이 다리를 건너는 최단 시간을 출력하라. (단, 트럭의 순서는 변경할 수 없으며 트럭의 무게는 서로 같지 않을 수 있다. 또한 트럭들은 하나의 단위 시간에 하나의 단위 길이만큼만 이동할 수 있다고 가정한다.)

 

😖 내가 생각한 로직 + 알고리즘

현재 다리 위에 있는 트럭의 무게를 group 변수에 저장하고, 현재 다리 위에 있는 트럭들의 첫 번째 트럭 순서 정보를 startTruck 변수에 저장한다. 또한 다리 위에 올라가지 못한 트럭들 중 가장 순서가 빠른 트럭의 순서 정보를 nextTruck 변수에 저장한다. 그리고 nextTruck 변수의 값이 n과 같거나 작은 동안 아래의 과정을 반복한다.

• nextTruck의 무게를 group에 더했을 때, 제한 하중(L)을 초과하지 않는다면 포함시킨다.
  • nextTruck += 1, needTime += 1
    • nextTruck 무게가 group에 더해졌다는 것은 다리 위에 올라갔음을 의미하는 것이므로 시간이 1초 흐른 것으로 초기화한다. 
• 만약 제한하중을 초과한다면 현재 형성된 group으로 다리를 건너야 하는 것이므로 startTruck이 다리를 완전히 건넌 것으로 되는 시점으로 needTime 변수 정보를 수정하고, group에서 startTruck의 무게를 제외시킨다.
  
  • 그리고 startTruck += 1

# n: 트럭의 수, w: 다리 길이, L: 다리의 최대 하중
n, w, L = map(int, input().split())
weights = [0]
weights += [i for i in map(int, input().split())]

startTruck = 1
nextTruck = 2
group =  weights[startTruck]
needTime =  1 

while nextTruck <= n:
    if group + weights[nextTruck] <= L and nextTruck - startTruck <= w:
        group += weights[nextTruck]
        nextTruck += 1
        needTime += 1
    else:
        needTime += w - (nextTruck - startTruck) + 1
        group -= weights[startTruck]
        startTruck += 1
        if group + weights[nextTruck] <= L:
            group += weights[nextTruck]
            nextTruck += 1

if needTime < w:
    needTime += w - (nextTruck - startTruck)

print(needTime + (n - startTruck + 1))

 

▶ 내 코드가 틀린 이유를 모르겠다.

 

 

🧐 참고한 코드

# n: 트럭의 수, w: 다리 길이, L: 다리의 최대 하중
n, w, L = map(int, input().split())
cars = list(map(int, input().split()))

# 큐를 이용해서 구현
# 처음에 다리의 길이만큼 0을 넣어준다 -> 차가 다리에 들어와서 나가는 거 시간 카운트할 수 있도록 빈 공간을 넣어준다.
q = deque()
for _ in range(w):
    q.append(0)

time = 0
idx = 0

while idx < n:
    time += 1
    q.popleft()

    # 지금 차 들어가도 다리 하중이 넘지 않는 경우
    if sum(q) + cars[idx] <= L:
        q.append(cars[idx])
        idx += 1
    # 넘으면 이전 차만 앞으로 가는 거고 빈공간이 생기는 거니까 0 넣어줌
    else:
        q.append(0)

# 다리에 차가 다 나가야 하므로 큐가 빌때까지
while q:
    time += 1
    q.popleft()

print(time)

(출처: https://velog.io/@mimmimmu/12%EC%A3%BC%EC%B0%A8-%EB%B0%B1%EC%A4%80-13335%EB%B2%88-%ED%8A%B8%EB%9F%AD-%ED%8C%8C%EC%9D%B4%EC%8D%AC)

 

📌 Python의 deque[데크] (from collections)

deque는 앞, 뒤에서 데이터를 처리할 수 있는 양방향 자료형으로 stack처럼 사용해도 되고 queue처럼 사용해도 된다. list와 매우 비슷하지만, appendLeft(x)와 popleft(x)와 같이 모듈에 내장된 함수가 존재하여 list에 비해 속도가 매우 빠르다.

▷ 예를 들어 list에서 첫 번째 요소 삭제를 위해 pop(0)을 사용하는 경우 시간복잡도는 O(N)이지만, deque에서는 popleft()를 사용하여 시간복잡도가 O(1)에 불과하다.

▶ 따라서 스레드 환경에서 안전하다는 장점을 가진다.

 

🤗 제출 후 pass한 코드

from collections import deque
# n: 트럭의 수, w: 다리 길이, L: 다리의 최대 하중
n, w, L = map(int, input().split())
weights = list(map(int, input().split()))
passed = []

q = deque()

q.append(weights[0])
weight_sum = weights[0]
i = 1

while i < n:
    # 다리 위가 꽉 찼을 때
    if len(q) >= w:
        passed.append(q.popleft())
        weight_sum -= passed[-1]
        continue
    if weight_sum + weights[i] <= L:
        q.append(weights[i])
        weight_sum += weights[i]
        i += 1
    else:
        q.append(0)  

for _ in range(len(q)):
    passed.append(q.popleft())

for _ in range(w):
    passed.append(0)
print(len(passed))

 

😎 앞으로의 개선 방향

 

이번 문제를 풀면서, 문제 풀이에 알맞는 자료구조에 대한 지식이 부족하다는 생각이 들었다. 또한 문제를 풀고나서도 내 코드가 참고한 코드보다 지저분한 것을 보니 코드를 좀더 가독성 좋게 짜는 연습도 많이 해야겠다는 생각이 들었다.😔