[프로그래머스] 다리를 지나는 트럭 JS (큐)

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

 

처음에 문제가 이해가 안 됐다. 몇번의 그림을 그리며 테스트케이스를 이해하려고 노력한 끝에 

다리를 건너는데 bridge_length만큼 시간이 걸린다는 것을 깨달았다.. (즉 다리를 bridge_length길이 배열이라고 본다면 1초에 1 인덱스씩 이동한다)

 

좋다 문제는 이해했는데 어떻게 풀지?

먼저 다리 양쪽으로 들어가고 나오니까 큐를 떠올렸다

큐를 순회하면서 모든 차량을 이동시키는데 필요한 시간을 ++한다.

이 때 탈출조건은 대기하고 있는 트럭이 없고 다리에 건너고 있는 트럭이 없을때까지이다 (= 모든 차량이 통과할때까지)

따라서 while( truck_weights.length ||  passing.length )

 

다리 위 맨 앞의 차량은 언제 다리를 통과할까?

처음에는 passing의 길이가 bridge_length보다 클 때를 생각하고 다음 트럭의 무게 혹은 0 을 passing배열에 push했다.

=> 이 방법의 문제는 0이 마지막 차량이 통과를 한 뒤에도 passing에 남아있어 while을 탈출하지 못 한다

 

passing의 길이말고 차량의 위치가 bridge_length를 넘어가는지 확인하기

passing에 [무게, 위치] 를 푸쉬해서 passing[0]의 위치가 bridge_length를 넘어가면 맨 앞 차량은 통과한거다

 

• 대기 중이거나 건너고 있는 트럭이 없을 때까지 순회
• 시간이 흐를때마다 다리 위 트럭들의 위치를 앞으로 한칸씩 이동한다
  • 이때 맨 앞 트럭의 위치가 다리를 벗어나면 passing에서 그 트럭을 빼고, 총 무게 합에서도 뺸다.
  • 맨 앞 트럭의 위치가 다리 안 이면 그대로 진행한다
• 다음 트럭을 더했을때 최대 무게 이하이면 passing에 다음 트럭을 push하고 총무게에 다음트럭무게를 더한다.

 

첫번째 풀이 (성공) - 시뮬레이션 접근

function solution(bridge_length, weight, truck_weights) {
    var answer = 0;
    let passing = [];
    let sum = 0; // 다리 위에 있는 차 무게의 합
    
    // 대기 트럭이 있던가 지나가고 있는 트럭이 있는 동안
    while(truck_weights.length || passing.length) {
        answer++; // 먼저 시간이 흐르고
        
        // 다리위의 트럭을 한칸씩 이동
        if (passing.length) {
            passing = passing.map(([w, i]) => [w, i+1]);
        }
        
        // 다리를 지나친 트럭이 있으면 빼준다
        if (passing.length && passing[0][1] > bridge_length) {
            const [w, location] = passing.shift();
            sum -= w;
        }
        
        // 다음 차가 올라올 수 있음 올라온다
        if (sum + truck_weights[0] <= weight) {
            const next = truck_weights.shift();
            sum += next;
            passing.push([next, 1]);
        }
    }
    return answer;
}

 

👍 두번째 풀이 (성공) - 큐

위의 풀이에서는 큐의 길이가 고정 되어있지 않아서 순회할때마다 차량의 위치를 수동적으로 이동시켜줘야했다 

다시보니 문제에 bridge_length가 주어진다 =>  고정된 배열을 만들어라

 

큐의 최대 길이가 10,000이므로 공간복잡도는 충분하고

큐의 길이가 고정되면 매번 map할 필요없이 shift, push만으로 차의 위치를 이동시킬 수 있다

 

// 나가고 들어가고 큐
// 길이 주어짐 큐 만듦
function solution(bridge_length, weight, truck_weights) {
    // 초기화
    const bridge = Array.from({length: bridge_length}, () => 0);
    const firstEnterW = truck_weights.shift();
    bridge.shift();
    bridge.push(firstEnterW);
    let sumW = firstEnterW; // 다리 위 총 무게
    var answer = 1;
    
    // 다리 위에 차가 있거나 아직 못 통과한 트럭이 있는 경우
    while(sumW > 0 || truck_weights.length) {
        // console.log(bridge)
        answer++; // 시간추가
        
        // 맨 앞 트럭 다리 통과
        sumW -= bridge.shift();
        
        // 다음 트럭 더 올릴 수 있는 경우
        const nextW = truck_weights[0];
        if (sumW + nextW <= weight) {
            sumW += nextW;
            truck_weights.shift();
            bridge.push(nextW);
        } else {
            // 다음 트럭 못 올리는 경우
            bridge.push(0);
        }
    }
    
    return answer;
}

 

느낀점

큐의 속성을 활용하니 코드도 간결하고 속도도 빠르다

자료구조의 중요성을 깨달았다.