[Python] 프로그래머스 Lv2_다리를 지나는 트럭

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

프로그래머스

 

• 정해진 순서대로 건넘
• 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return
• 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있음
• 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시
• bridge_length: 다리에 올라갈 수 있는 트럭 수
• weight: 다리가 견딜 수 있는 무게
• truck_weights: 트럭 별 무게

제한 조건

• bridge_length는 1 이상 10,000 이하
• weight는 1 이상 10,000 이하
• truck_weights의 길이는 1 이상 10,000 이하
• 모든 트럭의 무게는 1 이상 weight 이하

 

"""
입출력 예시)

bridge_length = 2, weight = 10, truck_weights = [7,4,5,6] -> 8
bridge_length = 100, weight = 100, truck_weights = [10] -> 101
bridge_length = 100, weight = 100, truck_weights = [10,10,10,10,10,10,10,10,10,10] -> 110
"""

 

# bridge_length = 2, weight = 10, truck_weights = [7,4,5,6]

 

 

문제 출처 p34~35

 

(회색 선: 다리 건너기 전 / 노란 선: 다리 지난 후)

(빨간 점선: 다리를 건너는데 필요한 시간 => bridge_length만큼)

# 경과 시간 1 -> 다리를 지난 트럭: x / 다리를 건너는 트럭: 7
# 경과 시간 2 -> 다리를 지난 트럭: x / 다리를 건너는 트럭: x (다리가 견딜 수 있는 무게가 10까지인데 이미 7인 트럭이 건너서)
# 경과 시간 3 -> 다리를 지난 트럭: 7 / 다리를 건너는 트럭: 4
# 경과 시간 4 -> 다리를 지난 트럭: 7 / 다리를 건너는 트럭: 4, 5
# 경과 시간 5 -> 다리를 지난 트럭: 7, 4 / 다리를 건너는 트럭: 5 (다리가 견딜 수 있는 무게가 10까지인데 이미 5인 트럭이 건너서)
# 경과 시간 6 -> 다리를 지난 트럭: 7, 4, 5 / 다리를 건너는 트럭: 6
# 경과 시간 7 -> 다리를 지난 트럭: 7, 4, 5 / 다리를 건너는 트럭: 6
# 경과 시간 8 -> 다리를 지난 트럭: 7, 4, 5, 6 / 다리를 건너는 트럭: x

 

## 의사코드 ##

# 선입선출 -> 큐

# bridge_length만큼 0으로 채운 큐 생성 => 다리
# while 대기 트럭이 있거나 이동 중인 트럭이 있는 경우: (그냥 len(truck_weights)하면 안됨 -> truck_weights가 이동 중인 트럭이 있을 수 있기 때문에)
#   다리를 다 지난 트럭을 큐(다리)에서 꺼냄
#   다리 위에 있는 트럭 무게 = 다리 위에 있는 트럭 무게 - 다리를 다 지난 트럭 무게
#   if 다리 위에 있는 트럭 무게 + 다음에 들어올 트럭 무게 <= weight: (다리 위에 있는 트럭 무게는 객체로 따로 생성)
#       다음에 들어올 트럭을 큐(다리)에 삽입
#       다리 위에 있는 트럭 무게 = 다리 위에 있는 트럭 무게 + 새로 다리에 들어온 트럭
#   else: 
#       continue

 

 

통과한 코드

 

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0 # 시간
    bridge_q = deque([0 for _ in range(bridge_length)]) # bridge_length만큼 0으로 채운 deque => 다리
    sum = 0 # 다리 위에 있는 트럭 무게 

    # 대기 트럭이 있거나 이동 중인 트럭이 있는 동안 반복
    while len(truck_weights) or sum > 0: 
        passed_truck = bridge_q.popleft() # 다리를 지난 트럭 꺼냄
        sum -= passed_truck # 다리 위에 있는 트럭 무게 - 다리를 지난 트럭

        # 새 트럭이 다리에 올라갈 수 있는 경우
        if len(truck_weights) and sum + truck_weights[0] <= weight: # truck_weights에 있는 트럭의 개수와 (다리 위에 있는 트럭 무게 + 새로 들어올 트럭의 무게)가 weight 보다 작거나 같으면
            new_truck = truck_weights.pop(0) # 새로 다리에 들어온 트럭
            bridge_q.append(new_truck) # 다리(bridge_q)에 새로 다리에 들어온 트럭 삽입
            sum += new_truck # 다리 위에 있는 트럭 무게 + 새로 다리에 들어온 트럭
        # 새 트럭이 다리에 올라갈 수 없는 경우
        else:
            bridge_q.append(0) # 다리(bridge_q)에 0을 삽입해서 다리 길이 유지
        
        answer += 1

    return answer

 

-> 다리인 큐를 deque가 아니라 queue.Queue()로 변경하면 시간초과

-> 다리 위에 있는 트럭 무게를 sum()으로 구하면 시간초과 + queue.Queue()로 만들었을 때는 sum() 사용 불가

-> if문에서 'len(truck_weights) and' 없으면 IndexError 발생

 

• and 조건
  • A and B 
  • => A와 B 둘 다 참이어야 조건 성립
• or 조건
  • A or B
  • => A 또는 B 둘 중 하나라도 참이면 조건 성립

 

참고)

 

https://afsdzvcx123.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%ACPython-%ED%8C%8C%EC%9D%B4%EC%8D%AC-AND-OR-NOT-%EC%A1%B0%EA%B1%B4-%EC%82%AC%EC%9A%A9%ED%95%98%EA%B8%B0

[파이썬(Python)] 파이썬 AND, OR, NOT 조건 사용하기

 

https://latte-is-horse.tistory.com/130

[프로그래머스 lv2] 다리를 지나는 트럭 (파이썬)