[프로그래머스 | 파이썬 / 자바스크립트] 다리를 지나는 트럭(스택/큐 / level 2)

문제

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

프로그래머스

 

 

🐍파이썬

❌ 실패한 코드

from collections import deque
def solution(bridge_length, weight, truck_weights):
    answer = 0
    truck_weights = deque(truck_weights)
    ing = deque(0 for i in range(bridge_length))
    while ing:
        answer += 1
        ing.popleft()
        if truck_weights: 
            if sum(ing) + truck_weights[0] <= weight:
                ing.append(truck_weights.popleft())
            else:
                ing.append(0)
    return answer

 

테스트케이스 5번 시간초과. sum의 시간복잡도가 O(n)이라서 발생하는 문제라고 한다.

참고한 블로그: https://jminie.tistory.com/157

from collections import deque
def solution(bridge_length, weight, truck_weights):
    answer = 0
    truck_weights = deque(truck_weights)
    ing = deque(0 for i in range(bridge_length))
    check = 0
    while ing:
        answer += 1
        check -= ing.popleft()
        if truck_weights: 
            if check + truck_weights[0] <= weight:
                ing.append(truck_weights.popleft())
                check += ing[-1]
            else:
                ing.append(0)
    return answer

ing: 다리를 건너는 중인 트럭을 나타내기 위해 다리의 길이만큼 0을 채운 deque이다.

check: 현재 다리를 건너는 중인 트럭의 무게를 체크하기 위한 변수, ing 배열 내 원소의 합

1️⃣ ing내에 원소가 남아있지 않을 때까지 while문을 돌면서 truck_weights의 원소를 한 개씩 ing로 옮긴다.

2️⃣ truck_weights 내에 원소가 존재하지 않는다면 ing값을 하나씩 popleft하여 빼주면서 다리를 건너는 단계를 표현한다. check값을 통해 다음 트럭을 다리에 이동시킬지말지 결정하므로, ing값을 popleft할때마다 check변수에서도 해당 값을 빼주어야 한다.

3️⃣ truck_weights 내에 원소가 존재한다면 현재 ing 배열의 sum과 다음 트럭원소의 합이 weight(다리가 견딜 수 있는 무게)보다 작거나 같을 때에만 트럭의 다음 원소를 ing에 추가한다. 추가된 원소의 값만큼 check값도 증가시켜준다. 만약 현재 ing 배열의 sum과 다음 트럭원소의 합이 다리가 견딜 수 있는 무게를 초과한 값이라면 트럭 원소값 대신 0을 추가하여 차를 혼자 보내도록 한다.

4️⃣ while문을 반복하는 동안 answer += 1을 진행하여 차의 이동 시간을 구하고, while문이 끝나면 answer값을 리턴한다.

 

while문을 한번 돌때마다 ing 출력값은 아래와 같다.

...
    while ing:
        answer += 1
        check -= ing.popleft()
        if truck_weights: 
            if check + truck_weights[0] <= weight:
                ing.append(truck_weights.popleft())
                check += ing[-1]
            else:
                ing.append(0)
        print(ing)
        # truck_weights = [7,4,5,6], weight = 10, bridge_length = 2
        # deque([0, 7])
        # deque([7, 0])
        # deque([0, 4])
        # deque([4, 5])
        # deque([5, 0])
        # deque([0, 6])
        # deque([6])
        # deque([])
    return answer

 

 

🐥자바스크립트

function solution(bridge_length, weight, truck_weights) {
    var answer = 0;
    //ing: 다리를 건너는 중인 트럭을 나타내기 위해 다리의 길이만큼 0을 채운 배열
    let ing = Array(bridge_length).fill(0);
    //check: 현재 다리를 건너는 중인 트럭의 무게를 체크하기 위한 변수, ing 배열 내 원소의 합
    let check = 0;
    while(ing.length > 0){
        answer++;
        check -= ing.shift();	//다리 앞의 부분을 삭제, check(ing 배열 원소 합)에서 ing[0]값을 빼기
        if(truck_weights.length > 0){	//추가할 원소가 있다면
            if(check + truck_weights[0] <= weight){	//check + 다음에 들어올 트럭 값이 다리가 감당할 수 있는 값이라면
                ing.push(truck_weights.shift());	//새로운 트럭을 다리 위에 올리기
                check += ing[ing.length - 1];	//check에 새로운 원소의 값을 +
            } else {	//다리가 무너질 것 같으면
                ing.push(0);	//트럭을 올리지 말고 0을 push해서 기존 트럭만 다리를 지나게 한다.
            }
        } //추가할 원소가 더 이상 없다면 ing.shift만 진행해서 다리 위의 트럭을 차례로 육지로 보낸다.
    }
    return answer;
}

 

 

다른 풀이 방법

function solution(bridge_length, weight, truck_weights) {
  // '다리'를 모방한 큐에 간단한 배열로 정리 : [트럭무게, 얘가 나갈 시간].
  let time = 0, qu = [[0, 0]], weightOnBridge = 0;

  // 대기 트럭, 다리를 건너는 트럭이 모두 0일 때 까지 다음 루프 반복
  while (qu.length > 0 || truck_weights.length > 0) {
    // 1. 현재 시간이, 큐 맨 앞의 차의 '나갈 시간'과 같다면 내보내주고,
    //    다리 위 트럭 무게 합에서 빼준다.
    if (qu[0][1] === time) weightOnBridge -= qu.shift()[0];

    if (weightOnBridge + truck_weights[0] <= weight) {
      // 2. 다리 위 트럭 무게 합 + 대기중인 트럭의 첫 무게가 감당 무게 이하면 
      //    다리 위 트럭 무게 업데이트, 큐 뒤에 [트럭무게, 이 트럭이 나갈 시간] 추가.
      weightOnBridge += truck_weights[0];
      qu.push([truck_weights.shift(), time + bridge_length]);
    } else {
      // 3. 다음 트럭이 못올라오는 상황이면 얼른 큐의
      //    첫번째 트럭이 빠지도록 그 시간으로 점프한다.
      //    참고: if 밖에서 1 더하기 때문에 -1 해줌
      if (qu[0]) time = qu[0][1] - 1;
    }
    // 시간 업데이트 해준다.
    time++;
  }
  return time;
}

풀이하신 분이 친절하게 주석을 달아주셨다.