Programmers_다리를 지나는 트럭

HKTUOHA·2023년 9월 3일
0

알고리즘 문제

목록 보기
9/15
post-thumbnail

📌문제



📌코드

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge = deque([0] * bridge_length)                  # 리스트보다 덱이 빠름
    truck_weights = deque(truck_weights)
    sum_weight = 0
    
    while bridge: 
    	# 첫 시작은 0 이지만, 이후를 위해 편의상 arrive로 정의
        arrive = bridge.popleft()          
        
        # 다리 끝에 도착하면 bridge 덱에서 빼주면서 
        if arrive > 0: 
        	# 다리 위 무게 합에서도 빼준다
            sum_weight -= arrive                         
        answer += 1
        
        if truck_weights:       
        
        	# 다리 위 무게 합 + 첫번째 대기 트럭 <= 최대 무게
            if sum_weight + truck_weights[0] <= weight:  
            
            	# 첫번째 대기 트럭을 다리 위에 올리고 다리 위 무게 합에 더한다
                land = truck_weights.popleft()           
                bridge.append(land)                      
                sum_weight += land      
                
            # 최대 무게보다 크면 뒤에 0 추가
            else:                                                     
                bridge.append(0)                         
        
    return answer

❌오답

  • 테스트케이스 5번 시간초과
# 테스트케이스 5번 시간초과
def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge = [0] * bridge_length
    
    while bridge:
    	# 다리 맨 앞의 자리 빼기
        bridge.pop(0)                                    
        answer += 1
        
        # 대기 트럭이 있을 때         
        if truck_weights:          
        	# 다리 위 무게 + 첫번째 대기 트럭 무게 <= 최대 무게
            if sum(bridge) + truck_weights[0] <= weight:  
             	# 다리에 첫번째 대기 트럭 추가
                bridge.append(truck_weights.pop(0))    
            # 최대 무게보다 크면                 
            else:         
            	# 다리에 0 추가
                bridge.append(0)                          
        
    return answer

⇒ 다리 위 무게의 합을 구할 때 sum( ) 함수를 사용하지 않고 +, - 로 계산하면 통과


📌마무리

풀이과정은 코드에 주석으로 달려 있으며, 혼자 풀지 못함🙁
정답은 다리에서 빼는 것부터 생각했다면, 나는 다리 위에 올리는 것부터 생각했다.
즉, 다리가 빌 때까지 (while bridge)가 아니라 대기 트럭이 없을 때까지 (while truck_weights)로 시작했다.
너무 복잡하게 생각하지 말고 효율적으로 생각해보자🤔

profile
공부 기록

0개의 댓글