programmers(44)level_2(다리를지나는트럭)

작성일 | In

문제: 44. 다리를 지나는 트럭

  • 모든 트럭이 일차선 다리를 건너려면 최소 몇 초가 걸리는가
  • 트럭은 1초에 1만큼 움직이며, 다리길이는 bridge_length, 무게는 weight까지 견딘다.
  • 길이가 2이고, 10kg인 무게를 견디는 다리가 있다.

  • 무게가 [7,4,5,6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 한다.

    경과 시간 /다리를 지난 /트럭 다리를 건너는 /트럭 대기 트럭 0 [][] [7,4,5,6] 1~2 [][7] [4,5,6] 3 [7][4] [5,6] 4 [7][4,5] [6] 5 [7,4][5] [6] 6~7 [7,4,5][6] [] 8 [7,4,5,6][] []

    따라서 8초가 된다.

  • 제한 조건
  • birdge_legnth는 1 이상 10000이하다.
  • weight은 1이상 10000이하이다
  • 모든 트럭의 무게는 1이상 weight이하다

접근 방안

  • 순서대로 최단 시간 안에 다리를 건너야 하며, 그 다리 또한 일차선 다리이다.
  • 즉 주어진 조건대로 문제를 수행하기만 하면 된다.

  • 입력값은 다리길이, 다리가 견딜 수 있는 최대 하중, 트럭의 무게 3개가 주어진다.

  • 쪼개서 생각해보자
  • 다리를 지나고 있는 트럭의 배열 만들자
  • Q) 언제 트럭이 이 배열 안으로 들어올 수 있을까 ?(다리로 출발이 가능할까?)
    • ( 다리의 최대 하중 - 현재 지나고 있는 트럭 무게 ) > 대기트럭 [0]의 수(무게)
  • Q) 경과 시간은 어떻게 계산해줄 수 있을까 ?
    • while문을 돌면서, 대기 트럭이 none이 아니고, 다리를 건너는 트럭 배열이 none이 아닐 때까지 반복
    • 변수를 하나 두고, 반복한 횟수를 센다.
  • Q) 그렇다면 경과 시간이 2가 되었을 때, 출발한 자동차를 언제 pop을 해주지 ?
    • 그걸 잘 모르겠다.
    • 자동차와 경과시간을 튜플로 묶어서 저장한 뒤, 경과시간이 2인 것들만, 조건문을 통해서 빠져나가게 하면 되지 않을까?
    • 이게 문제에서 의도하고 있는 접근이 아닌 것 같다..

다른 분들의 코드를 결국 참고했다

  • 힌트만 가져와봤다.
  • 다리의 길이만큼 q를 0으로 채운다. -> 이 생각을 전혀 못했다.
  • 시간은 0초부터 시작
  • 다리가 있는 동안 반복
  • 매 루프마다 1초씩 더한다
  • q의 맨 앞 값을 pop하는 이유는 트럭이 지나감을 표현하기 위해서다
  • 트럭 배열이 있다면
    • 다리에 있는 트럭 무게+대기 중인 트럭 무게<=한계 무게인 경우, 대기 중인 트럭을 다리에 싣는다.
    • 다리의 하중 초과면 q에 0을 넣어서 트럭을 왼쪽으로 이동시킨다. - 트럭의 이동을 0을 넣어서 진행시킨다.

코드

def solution(bridge_length, weight, truck_weights):
    q = [0] * bridge_length
    sec = 0
    while q:
        sec += 1  # 시작했으니 1초를 더한다.
        q.pop(0)  # 시간의 경과에 따른 트럭의 이동
        if(truck_weights):
            if sum(q) + truck_weights[0] <= weight:
                q.append(truck_weights.pop(0))
            else:
                q.append(0)
    return sec

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

이것을 몰라서 구현을 못했다.

  • 알면 정말 쉽고. 모르면 어렵다.
  • q에 다리의 길이를 넣어서 초기화 시켜준 것
  • 자동차의 이동을 0을 append하고 pop(0) 한 것으로 표시해준 것
  • while 문의 조건절에 q를 넣은 것

참고자료 [참고블로그]https://oneshottenkill.tistory.com/340 [프로그래머스]https://programmers.co.kr/learn/challenges

0%