[코테] 다리를 지나는 트럭 (스택/큐)

다리를 지나는 트럭 (스택/큐)

2026.4.14, 2026.4.15 (작성일: 2026.4.16)

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

핵심 개념

• '일차선 다리' = "큐": 선입선출의 구조
• 다리에 올라가있는 트럭의 무게의 합 = reduce 돌리지 않아도, 트럭이 올라가고 내려가는 처리를 해줄 때 무게 변수에 더하고 빼주면 관리 가능
• 다리에서 내려가는 것부터 처리, 그후 올라올 수 있는지 체크
• 트럭이 다리에 올라갈 수 있는 조건 = 현재 무게 + 올리려는 트럭의 무게 <= 수용 가능한 무게
• 트럭을 다리에서 내려야 하는 순간을 계산할 때, '트럭이 올라온 시간(초)'를 알고 있어도 계산 가능하지만, '트럭이 내려가야 하는 시간(초)'를 저장하면 코드가 더 깔끔해짐
  트레이싱 해보면 트럭이 내려가야 하는 순간 = queue에 속한 시간이 bridge_length만큼일 때이므로, 현재 시간 = 다리에 올라온 시간 + bridge_length 가 true이면 내려가야 함
• 위 접근법과 이어지는데, seconds 증가 처리 위치는 저장하는 시간의 개념에 따라 달라짐
  1. "진입 시점"을 저장할 경우 -> 나가야 하는지 조건을 체크하기 위해 이 '진입 시점' 값을 이용해 duration, 거리를 계산해야 함. 트럭이 0초에 올라온건지 1초에 올라온건지 생각해보면 됨..
  2. "나갈 시점"을 저장할 경우 -> 나가야 하는지 조건을 체크할 때 반복문 안의 seconds와 저장했던 '나갈 시점'(seconds + bridge_length)이 "같은지" 단순 비교만 하면 됨 (지금 시간이 내가 나가야 할 시간과 같은가)
• 시간 효율성: 테스트 케이스에 다리가 수용 가능한 무게가 100kg인데 트럭은 10kg 1개만 존재하는 경우가 있음. shift, push만 처리하는 반복문 구현 시 이 케이스는 트럭 1개가 다리에 올라가있고 다른 변화는 없는 상태로 루프를 100번 돌고 seconds를 0부터 101까지 증가시키는 작업만 수행함.
  이런 경우 현재 올라가있는 트럭이 내려가는 시간으로 seconds를 증가시켜 그 다음 순간의 루프를 실행할 수 있도록 개선해 효율성 확보 가능

내 풀이

function solution(bridge_length, weight, truck_weights) {
    let seconds = 0;
    let currentWeight = 0;
    const queue = []; // [무게, 진입한 시점의 초][]
    
    // 두 배열이 모두 비어있을 때까지 진행
    while (queue.length > 0 || truck_weights.length > 0) {
        // seconds 증가 // ⚠️ "진입한 시점의 초"를 저장해야 해서 시간을 먼저 증가시켜줘야 아래 로직이 올바르게 동작함
        seconds += 1;
        
        // shift 조건 체크
        if (queue.length > 0) {
            const duration = seconds - queue[0][1];
            if (duration === bridge_length) {
                const item = queue.shift();
                currentWeight -= item[0];
            }
        }
        
        // push 조건 체크
        if (currentWeight + truck_weights[0] <= weight) {
            queue.push([truck_weights[0], seconds]);
            const item = truck_weights.shift();
            currentWeight += item;
        }
    }
    
    return seconds;
}

1. 이전에 다른 문제 풀이 시도 때처럼 인덱스를 따로 저장하는 식으로 접근하려 하지 않고, queue 배열에 트럭의 무게와 시간을 함께 저장하려 한 것!! 장족의 발전이다. 처음엔 객체 형태로 저장하려 했는데 키 없이 값만 넣어서 {무게, 시간}으로 쓰고 문법 오류를 만났다. 고민하다가 배열을 선택했다..
2. seconds 같은 변수는 루프 안 모든 작업 처리 후 마지막에 증가시키는 것이 관행이지 않은가? 나도 그렇게 작성했었는데, 트럭이 머무는 시간이 부정확하게 계산됐다.
   => 첫번째 트럭은 0초가 아닌 1초에 올라왔는데 0초에 올라온 것으로 저장되어서 계산이 이상해진 것
   "진입한 시점의 초"를 저장하기로 했기 때문에, 루프 안의 계산을 실행하기 전에 seconds를 먼저 증가시켜줘야 현재 시간을 의도대로 저장할 수 있었다.
3. 그 외에는, currentWeight (다리 위 트럭 무게의 합)를 변수로 관리하는 것, queue에서 트럭이 내려가야 할때(먼저)와 올라갈 수 있을 때(내려간 뒤)를 순서대로 체크하고 처리해주는 것. 사실 무게의 합이 필요하다 = reduce 써야지, 다른 방법이 있나? .. 딱히 없군! 생각하고 push 조건 체크하는 if문에서 reduce를 썼는데, 매 순회마다 queue의 모든 요소를 순회하는 메서드를 쓰는 격이라 시간 초과로 실패했었다. 어떻게 접근할지 고민하던 중 창밖 도로를 지나가는 차들이 접근 방식 변경에 도움을 주었다. (올라오고 내려가는 것을 처리할 때 무게 변수도 같이 관리해주면 되는구나!)

개선된 풀이

function solution(bridge_length, weight, truck_weights) {
    // '다리'를 모방한 큐. [트럭 무게, 다리에서 나가야 하는 시간][] // ✅ 저장할 개념을 변경함
    const queue = [];
    let seconds = 0;
    let weightOnBridge = 0; // ✅ 더 직관적인 네이밍이라서 차용
    
    // 다리를 건너는 트럭, 대기 트럭이 모두 0일 때까지 다음 루프 반복
    while (queue.length > 0 || truck_weights.length > 0) {
        // 1. 현재 시간이 다리 위 첫번째 트럭의 나갈 시간과 같다면,
        //    첫번째 트럭을 나가게 하고, 다리 위 무게에서 뺌  // ✅ 코테에서도 가독성 좋은 주석을 작성할 수 있구나 느껴서 차용
        if (queue[0] && seconds === queue[0][1]) { // ✅ queue를 [[0, 0]]으로 초기화해주면 queue[0]이 존재하는지 체크할 필요가 없지만, 저 초기화가 어떤 의미인지 와닿지 않아서 조건문 안에서 체크하도록 작성
            weightOnBridge -= queue.shift()[0]; // ✅ 배열 요소의 첫번째 값이 '무게'임
        }
        
        // 2. 대기 트럭이 올라와도 다리가 견딜 수 있는 무게라면,
        //    대기 트럭을 올리고, 다리 위 무게에 더함
        if (weightOnBridge + truck_weights[0] <= weight) {
            queue.push([truck_weights[0], seconds + bridge_length]); // ✅ 트럭이 내려갈 시점을 저장하는 방식
            weightOnBridge += truck_weights.shift();
        } else { // ✅ 이 부분이 실행 시간 단축의 키 - 없어도 통과하지만, 실무였으면 퍼포먼스 향상에 큰 도움이 됐을 코드..
            // 3. 대기 트럭이 못 올라온다 = 다리 위 트럭이 나가줘야 함
            //    다리 위 첫번째 트럭이 나갈 수 있는 시간으로 점프하여 효율성 확보
            if (queue[0]) { // ✅ 마찬가지로 queue가 비어있지 않아야 아래 코드가 안전히 처리될 수 있음
                seconds = queue[0][1] - 1; // 루프 밖에서 1초 증가시키므로 -1 처리 // ✅
            }
        }
        
        // 4. 모든 작업 완료 후 seconds 증가
        seconds ++; // ✅ 트럭이 내려갈 시점을 저장하므로 시간을 마지막에 증가시키는 것이 맞음
    }
    
    return seconds;
}

핵심 차이

1. 저장할 개념 변경: 올라온 시점 -> 내려갈 시점
2. 네이밍과 주석 - '다른 사람의 풀이' 보고 사실 좀 많이 놀랐음. (아래에 첨부) 코테는 혼자 보는 거라 생각하고 문제 푸는 것에만 집중하면 된다고 생각했는데.. 단적으로 나는 주석을 두 배열이 모두 비어있을 때까지 진행이라 썼음. 그건 코드 보면 알 수 있는 내용인데 굳이 적은 이유는 풀면서 내 사고를 명확히 하려는 의도. 그런데 그 풀이에서는 동일한 부분에 대기 트럭, 다리를 건너는 트럭이 모두 0일 때 까지 다음 루프 반복이라 적었음. 문제에서 주어진 상황과 코드 설명을 적절히 작성한 것 같아 놀랐다. 다만 나는 아직은 주석 작성에 더 신경을 쓰기보단 문제 풀이, 접근법에 더 집중할 때가 맞다. 그래도 가능하면 이런 식으로 적어볼까 싶다! (협업할 때도 이런 주석이 코드 파악에 도움이 되니까 언제 코드를 쓰든 그런 습관을 들이도록 연습하려는 의도다.)
3. 좀더 간략해진 것은 당연한 것이고 - 나는 처음 풀때는 의도적으로 변수들을 더 선언하는 편이다. 그 변수 이름에 의도를 반영해두는 편.. 그리고 통과하면 불필요한 변수 정의를 줄여나가는 식으로 하는데, 뭐가 더 나을지는 아직 고민이다.
4. 시간 단축을 위한 점프 부분. 생각도 못한 지점이다. 문제 풀이 + 통과만을 목적으로 했는데, 이런 식으로 실행 시간을 줄일 방법을 생각해낼 수도 있구나 신기했다. 그 의도까지 적혀있는데 뭔가 완벽한 코딩테스트 응시자의 전형을 본 것 같아 굉장히 인상깊었다. (이 코드 바탕으로 이야기 나눌 때 저렇게 말할 것 같고, 문제 출제자가 너무 만족할 답변일 것 같단 생각..)

막혔던 포인트

위에 다 적어놔서 반복이니 간략히만 정리한다.

• 다리 위 무게의 합을 구할 방법
• push 조건을 정확히 체크할 방법
• queue에 무게와 함께 저장할 시간을 어떤 걸로 할 것인가 & 나갈 시점 체크를 어떻게 할 것인가 => seconds를 언제 증가시켜야 하는가로 이어지는 결정

풀면서 찾은 개념

검색은 딱히 안했음

다음에 비슷한 문제 만나면

• 트럭 무게와 진입 시간을 묶어서 저장하기로 생각해낸 것처럼, 쌍으로 존재하면 더 도움이 되는 경우인지 체크해보자
• seconds 증가 코드의 위치를 변경했을 때처럼 나의 직관과 맞지 않는 테스트 결과가 나올 땐, 접근 방식, 내가 저장하고 사용하는 변수의 개념을 다른 걸로 변경해볼 순 없을지 고민해보자
• 반복문 안에서 추가로 조건 체크를 할 때는 배열의 모든 요소를 순회하는 메서드 대신 더 단순한 방법은 없을지 고민하자
• 주어진 문제 풀이 플러스 알파로 문제의 조건 자체에서 실행 시간을 단축시킬 방법이 있을지 고민해보는 것도 좋겠다
• 주석과 네이밍도 좀더 신경써보자