Coding Test/Programmers

다리를 지나는 트럭 (Bridge Truck)

JTB 2025. 10. 14. 20:06

난이도: level 2

링크: Programmers 42583 - 다리를 지나는 트럭

풀이 날짜: 2025.10.14 - 중간에 집중이 흐트러졌으나, 어쨌든 끝까지 감

 

1. 문제 이해

 

트럭 여러 대가 무게 제한이 있는 다리를 일정 시간 동안 건너는 시뮬레이션 문제다.

모든 트럭이 다리를 건너는 데 걸리는 총 시간을 구해야 한다.

 

조건은 다음과 같다.

  • 다리는 한 번에 여러 대의 트럭이 올라갈 수 있다.
  • 다리 위 트럭의 총 무게가 weight 이하여야 한다.
  • 각 트럭은 1초에 1칸씩 전진한다. (설명에는 없으나 입출력 예를 참고)
  • 다리 길이는 bridge_length로 주어지고, 트럭이 다리를 완전히 건너는 데에는 bridge_length초가 걸린다.

 

2. 접근 아이디어 및 자료구조

이 문제는 단순히 트럭을 한 칸씩 움직이는 시뮬레이션 문제처럼 보이지만, 사실상 Queue(큐) 기반으로 해결할 수 있는 구조다.

시간을 업데이트 하는 라운드의 기준과 그리고 그 라운드에서 어떤 처리를 할 것인지에 대해서 고민하는데 시간을 많이 썼다. 순서도 중요함!

 

핵심 포인트는 다음과 같다.

  1. Queue로 다리 상태를 표현한다. - 다리 위에 올라간 트럭들의 무게(weight)와 위치(step)를 함께 관리한다.
  2. 매 초(time++)마다 모든 트럭의 step을 1씩 증가시킨다.
  3. step > bridge_length가 된 트럭은 다리를 완전히 건넜으므로 shift()로 제거한다.
  4. 다음 트럭을 올릴 수 있는 조건(총무게 + 다음트럭 ≤ weight)을 만족하면 다리에 진입시킨다.
  5. 다리 위와 대기 중 트럭이 모두 사라질 때까지 반복한다.

 

 

3. 풀이코드

나의 코드

1. 선입선출인 큐 구조라는 것을 명심. 다리에서 트럭을 내보내거나 bridge[0], 다리에 새 트럭을 추가할 때 truck_weights[0],

0번째 인덱스의 요소가 타겟이 되어야 한다.

2. "다리위 트럭 이동 -> 다리위 첫 트럭의 탈출여부(한 라운드에 하나씩만 나갈수 있음) 확인 -> 새 트럭 가능여부 확인" 순으로 동작하도록 코드 작성

3. 각 트럭의 이동거리(step) 와 중량(weight) 을 상태로 저장하여 사용

function solution(bridge_length, weight, truck_weights) {
    var time = 0;
    const bridge = [];
    
    while (bridge.length > 0 || truck_weights.length > 0) {
            // 다리의 모든 트럭 이동
            bridge.forEach(v => {
              const newStep = v.step + 1;
              v.step = newStep;
            })
        
            // 다리위 첫번째 트럭의 탈출 여부 확인
            const target = bridge[0];
            if(target && target.step > bridge_length) {
                bridge.shift();               
            }
        
            const bridgeWeight = bridge.reduce((acc, cur)=> acc + cur.weight,0);
            
            // 다리에 트럭 추가 가능여부 확인 후 새 트럭 추가
            if(weight >= bridgeWeight + truck_weights[0]) {                
                bridge.push({
                    step: 1,
                    weight: truck_weights.shift()
                });
            }    
            
            time++;
    }       
    return time;
}

 

ChatGPT 개선코드

코드가 훨씬 깔끔해졌다. 

function solution(bridge_length, weight, truck_weights) {
    let time = 0;
    const bridge = []; // 다리 위 트럭: { weight, step }

    while (bridge.length > 0 || truck_weights.length > 0) {
        time++;

        // 1️⃣ 다리 위 트럭 이동
        bridge.forEach(truck => truck.step++);

        // 2️⃣ 다리 끝 도착한 트럭 제거
        if (bridge.length > 0 && bridge[0].step > bridge_length) {
            bridge.shift();
        }

        // 3️⃣ 새 트럭 진입 조건 확인
        const nextTruck = truck_weights[0];
        const bridgeWeight = bridge.reduce((sum, t) => sum + t.weight, 0);

        if (nextTruck !== undefined && bridgeWeight + nextTruck <= weight) {
            bridge.push({ weight: nextTruck, step: 1 });
            truck_weights.shift();
        }
    }

    return time;
}

 

 

5. 예시 시뮬레이션

bridge_length = 2
weight = 10
truck_weights = [7,4,5,6]
시간 다리 위 상태(step, weight) 다리 총 무게 대기 트럭 비고
1초 [{w:7, s:1}] 7 [4,5,6] 첫 트럭 진입
2초 [{w:7, s:2}] 7 [4,5,6] 이동 중
3초 [{w:4, s:1}] 4 [5,6] 7이 다리 통과 후 4 진입
4초 [{w:4, s:2}, {w:5, s:1}] 9 [6] 두 번째 트럭 진입
5초 [{w:5, s:2}] 5 [6] 4 통과
6초 [{w:6, s:1}] 6 [] 마지막 트럭 진입
7초 [{w:6, s:2}] 6 [] 이동 중
8초 [] 0 [] 마지막 트럭 통과 ✅

 

총 8초 소요.

구분 복잡도 설명
시간 복잡도 O(n) 각 트럭을 한 번씩 처리
공간 복잡도 O(n) bridge 배열과 truck_weights 관리

 

6. 정리

포인트 설명
핵심 구조 Queue 기반 시뮬레이션
이동 방식 매 초마다 step + 1
제거 조건 step > bridge_length
추가 조건 총 무게 + 다음 트럭 ≤ weight

이 문제의 포인트는 “트럭의 이동을 직접 구현하지 않고, 시간 단위로 상태를 업데이트한다”는 것이다.

즉, 물리적으로 움직이는 것을 큐의 상태 변화로 추상화해 현실적인 문제를 깔끔한 알고리즘 형태로 풀어내는 게 핵심이다.