[프로그래머스 / Python] 다리를 지나는 트럭 | 초코더

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

코딩테스트 연습 - 다리를 지나는 트럭

 

문제

다리길이, 다리가버틸수있는무게, 트럭여러대리스트가 주어지면

총 몇초뒤에 모든 트럭이 지날수있는지 구하는문제. 단, 트럭은 1초에 1만큼 움직일 수 있다.

 

접근법

처음에 문제 예시에 설명하는것처럼 원래트럭리스트, 지나고있는트럭리스트를 따로 두고

시간을 더해가면서 구하려고 했는데 그럴경우에 각 트럭이 길이를 얼만큼 지났는지 구하는게 굉장히 복잡했다.

다른사람의 풀이방법을 참고해보니 다리길이만큼 0을 채워준 리스트를 두고 트럭을 넣고 빼고하면서

구할 수 있었다. 

다리길이만큼 리스트를 선언해주고 트럭을 움직여준다는 생각 !!! 배웠습니당..

 

풀이

1. queue리스트에 다리길이만큼 0을 선언해준다. (이 리스트가 다리의 상황을 나타내줄것임)

2. queue리스트에 값을 하나씩빼주면서, 가능한 무게의 트럭을 담는다. (queue가 빌때까지)

   2-1. queue리스트에 값을 빼주고 더하면서 time을 더해주는 방식은 트럭이 다리를 움직이는 과정이다.

         그래서 queue리스트를 뽑아보면 반복문이 실행할때마다 트럭이 점점 오른쪽으로 움직이며 마지막엔

         빠져나가는 것을 볼 수 있다.

   2-2. 다리가버틸수있는 무게를 초과할 경우는 그냥 0을 담고 빼면서 트럭을 움직인다.

   2-3. 담을 수 있는 트럭이 하나도 안남을 경우, queue를 pop()하는 과정만 반복한다.(마지막트럭이 지나가는과정임)

 

전체코드

테스트케이스 하나가 시간초과가 나서 ,, 코드를 좀 수정한후에 다시 또 올려보겠습니다 !! 개선이 필요한 코드입니당

def solution(bridge_length, weight, truck_weights):
    time=0
    #queue를 다리 길이만큼 만들어주고
    queue=[0]*bridge_length

    while queue:
        time+=1
        queue.pop()
        #트럭이 빌때까지 뽑아줌
        if truck_weights:
            # 사용가능한 트럭무게만큼 들어오고 나가고 해서 구현
            if truck_weights[0]+sum(queue)<=weight:
                queue.insert(0,truck_weights.pop(0))
                #print(queue)
            else:
                queue.insert(0,0)
                #print(queue)

    return time

print(solution(10,10,[7,4,5,6]))

 

+추가코드

보니깐 sum()함수를 반복문돌때마다 실행해서 O(n)만큼 걸려서 시간초과가 난것같습니다..

그래서 sum()함수대신에 queue에서 빠져나가는 수를 빼주도록 바꾸어주었습니다.

def solution(bridge_length, weight, truck_weights):
    time=0
    #queue를 다리 길이만큼 만들어주고
    queue=[0]*bridge_length
    s_queue=0

    while queue:
        time+=1
        s_queue-=queue.pop()
        #트럭이 빌때까지 뽑아줌
        if truck_weights:
            # 사용가능한 트럭무게만큼 들어오고 나가고 해서 구현
            if truck_weights[0]+s_queue<=weight:
                s_queue+=truck_weights[0]
                queue.insert(0,truck_weights.pop(0))
                #print(queue)
            else:
                queue.insert(0,0)
                #print(queue)

    return time

print(solution(10,10,[7,4,5,6]))