다리를 건너는 트럭 (deque 모듈)

문제 설명

 

 

풀이

 

내가 짠 코드는

def _pass(length, truck_weights):  #다리 위에 트럭이 올라갈 때 명령
    length = length[1:]
    length.append(truck_weights[0])
    truck_weights = truck_weights[1:]
    truck_weights.append(0)
    return length, truck_weights 

def nun_pass(length):     #다리 위에 트럭이 질량을 초과할 때 명령
    length = length[1:]
    length.append(0)
    return length

def solution(bridge_length, weight, truck_weights):
    cnt = 1
    length = [0 for col in range(bridge_length)]  # bridge_length만큼 다리 길이를 유지
    length, truck_weights = _pass(length, truck_weights)
                     #일단 첫 번째 트럭을 다리 위에 올림
   
    while sum(length) != 0:
        if sum(length) + truck_weights[0] <= weight:
            length, truck_weights = _pass(length, truck_weights)
            cnt += 1 
        else:
            length = nun_pass(length)
            cnt += 1
            if sum(length) == 0 :  #다리 위에 트럭이 없어졌을 때 다음 트럭 당기기
                length, truck_weights = _pass(length, truck_weights)
                
    return cnt

샘플 테스트 케이스는 통과됐지만 정답은 아니었고, 시간을 초과한 경우도 있었다.

sum() 함수가 시간복잡도가 O(N)이기 때문이라 한다.

되도록 sum 함수를 쓰지않고 다른 방법을 찾다보니

deque 라이브러리를 사용하고, 새로운 변수를 두어 다리 위의 무게를 계산하든 sum을 없애는 쪽으로 다시 했다.

 

def _pass(length, truck_weights, mass):  
    mass -= length[0]              # 다리 끝에서 내리는 질량
    mass += truck_weights[0]       # 다리 시작에서 올라오는 질량
    length = length[1:]
    length.append(truck_weights[0])
    truck_weights = truck_weights[1:]
    truck_weights.append(0)
    
    return length, truck_weights, mass

def nun_pass(length, mass):     
    mass -= length[0]     # 다리 끝에서 내리는 질량
    length = length[1:]
    length.append(0)
    return length, mass

def solution(bridge_length, weight, truck_weights):
    cnt = 1
    mass = 0  #sum 함수를 없애기 위한 새로운 다리 위 질량 변수
    length = [0 for col in range(bridge_length)]  
    length, truck_weights, mass = _pass(length, truck_weights, mass)
                     #일단 첫 번째 트럭을 다리 위에 올림
    
    while mass != 0:
        if mass + truck_weights[0] <= weight:
            length, truck_weights, mass = _pass(length, truck_weights, mass)
            cnt += 1 
        else:
            length, mass = nun_pass(length, mass)
            cnt += 1
            if mass == 0 :  #다리 위에 트럭이 없어졌을 때 다음 트럭 당기기
                length, truck_weights, mass = _pass(length, truck_weights, mass)
                
    return cnt

이렇게 짜보았으나 역시 잘못된 코드였다.

===========================================================================

테스트 케이스를 추가해서 살펴봤다.  bridge_length = 5, weight = 50, truck_weights = [20, 10, 30, 50, 30]

로 선언했을 때, [ 현재 다리 위의 총 무게 + 다음 트럭 무게 ]  로 계산을 해서 weight를 초과하면 다음 트럭을 올리지 않았다. 이 문제를 해결하기 위해. 일단 다리 끝의 트럭을 내려놓고, ( 다리 위 총 무게 ) 연산을 해야했다.

def _pass(length, truck_weights, mass):           
    mass += truck_weights[0]       # 다리에서 트럭 내리는 부분을 삭제
    length.append(truck_weights[0])
    truck_weights = truck_weights[1:]
    truck_weights.append(0)
    
    return length, truck_weights, mass

def nun_pass(length, mass):     
    length.append(0)   # 다리에서 트럭 내리는 부분을 삭제
    return length, mass

def solution(bridge_length, weight, truck_weights):
    cnt = 1
    mass = 0  
    length = [0 for col in range(bridge_length)]  
    length, truck_weights, mass = _pass(length, truck_weights, mass)
    length = length[1:]    # 다리 길이 보정 해야함
                     
    print(length)
    while mass != 0:
        mass -= length[0]    #연산 전에 미리 다리 끝 트럭을 내린다
        length = length[1:]
        if mass + truck_weights[0] <= weight:
            length, truck_weights, mass = _pass(length, truck_weights, mass)
            cnt += 1 
        else:
            length, mass = nun_pass(length, mass)
            cnt += 1
            if mass == 0 : 
                length, truck_weights, mass = _pass(length, truck_weights, mass)
    return cnt

수정된 코드는 이렇다. 하지만

5번 케이스는 아슬아슬하게 통과했다.

===========================================================================

deque를 써서 짜봤다.

from collections import deque
def solution(bridge_length, weight, truck_weights):
    length = deque([0]*bridge_length)
    truck = deque(truck_weights)
    cnt = 1
    mass = 0
    
    mass += truck[0]       
    truck.append(0)
    length.append(truck.popleft())
    length.popleft()   #일단 첫번 째 트럭 올리기
    
    while mass != 0:
        mass -= length.popleft()  # 반복되는 행위, 앞으로 빼기
        cnt += 1
        
        if mass + truck[0] <= weight:
            mass += truck[0]       
            truck.append(0)
            length.append(truck.popleft())  #스택으로 값 빼기
        else:
            length.append(0)
            if mass == 0 :         
                mass += truck[0]       
                truck.append(0)
                length.append(truck.popleft()) #스택

    return cnt

 deque로 정의한 리스트(?)는 함수 안으로 들어갔을 때 list로 인식 돼서 deque의 함수인 popleft를 못 쓴다. 그냥 통으로 다시 짰다. 정답이 나온다.

5번 케이스도 무난하게 넘어간다.

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0    
    temp = 0
    truck_bridge_deque = deque(bridge_length * [0])
    truck_weights_deque = deque(truck_weights)

    while len(truck_bridge_deque):   # 다리 위 요소가 모두 사라질 때까지
        answer += 1 
        temp -= truck_bridge_deque[0] 
        truck_bridge_deque.popleft()   #다리 위 요소를 계속 없앤다
        if truck_weights_deque:  #트럭 리스트가 소모되면 실행 X
            if temp + truck_weights_deque[0] <= weight:  
                temp += truck_weights_deque[0]
                truck_bridge_deque.append(truck_weights_deque.popleft())
            else:     
                truck_bridge_deque.append(0)

    return answer

이렇게 짠 사람이 있었다. 아주 깔끔해 보인다.

 

- 나는 truck의 리스트를 요소 4개로 유지시켜줬지만 굳이 그럴 필요가 없었다. 

if temp + truck_weights_deque[0] <= weight:  를 판단할 때 [0] 번째 요소에 접근하기 위해 갱신 시켰지만,

그 위에 if문으로 실행을 하지 않게 만들어버리면 됐었다.

 

- 다리 길이를 줄이는 것으로 while 제한을 뒀다. 나는 다리 위 mass 값을 갱신해야했기에 while문 위에 초기에 트럭이 올라갔음을 따로 표현해주는 식이 필요했다. 억지로 끼워맞춘 느낌이 든다. while을 제한하기 위한 상황을 좀 더 외워두고 써먹어야겠다.

 

 

2주만에 다시 풀어봤다.

from collections import deque
def solution(bridge_length, weight, truck_weights):
    bridge = deque([0]*bridge_length)
    truck = deque(truck_weights)
    mass = 0
    cnt = 0
    
    while bridge:
        mass -= bridge[0]
        bridge.popleft()
        
        if truck and mass+truck[0] <= weight:
            mass += truck[0]
            bridge.append(truck.popleft())
        elif truck:
            bridge.append(0)
        cnt+=1
    
    return cnt

이전보다 확실히 코드가 간결해진 것이 보인다.

 

 

출처

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

프로그래머스