[프로그래머스] Level2 - 다리를 지나는 트럭(Javascript)

프로그래머스

▶ 문제 요약

1. 트럭 여러 대가 일차선 다리를 정해진 순으로 건너려한다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내라.

2. 다리에는 최대 bridge_legnth대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있다. 

3. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return해라.

 

▶ 코드

function solution(bridge_length, weight, truck_weights) {
	// 다리 = [트럭무게, 트럭이 나갈 시간]
	let time = 0, bridge = [[0, 0]], weightOnBridge = 0;
    
    // 다리를 건너는 트럭, 대기 트럭이 0이 될 때까지 루프
    while (bridge.length > 0 || truck_weights.length > 0) {
    	
        // 다리의 가장 앞에 있는 트럭의 나갈 시간과 현재 시간이 일치하면 내보내고
        // 다리 위 트럭 무게 합에서 나간 트럭의 무게를 빼준다.
        if (bridge[0][1] === time) weightOnBridge -= bridge.shift()[0];
        
        // 다리 위 트럭 무게 합 + 대기중인 트럭의 첫 무게가 무게 제한보다 아래라면
        if (weightOnBridge + truck_weights[0] <= weight) {
            // 다리 위 트럭 무게를 더해주고
            weightOnBridge += truck_weights[0];
            // 다리에 = [트럭무게, 현재 시간 + 다리를 완전히 건너기 위해 필요한 시간]
            bridge.push([truck_weights.shift(), time + bridge_length]);
        } else {
            // 만약 무게 제한보다 위라면 앞에 있는 트럭을 빼기 위해서
            // 가장 앞에 있는 트럭과 현재 시간을 맞춰준다
            // -1을 하는 이유는 곧바로 아래에 시간을 ++; 해주기 때문
            if (bridge[0]) time = bridge[0][1] - 1;
        }
        time ++;
    }
    return time;



}

▶ 풀이 과정

1. 문제 설명에 나와있는 예제 1번을 가지고 직접 과정을 보여주겠다.

시간 0: 초기 상태

• time = 0
• qu = [[0, 0]]
• weightOnBridge = 0
• truck_weights = [7, 4, 5, 6]

시간 1: 첫 번째 트럭(무게 7)이 다리에 올라간다.

• time = 1
• qu = [[0, 0], [7, 2]] (7kg 트럭이 시간 2에 다리를 건널 예정)
• weightOnBridge = 7
• truck_weights = [4, 5, 6]

시간 2: 첫 번째 트럭(무게 7)이 다리를 건너고 두 번째 트럭(무게 4)이 다리에 올라간다.

• time = 2
• qu = [[4, 4]] (4kg 트럭이 시간 4에 다리를 건널 예정)
• weightOnBridge = 4
• truck_weights = [5, 6]

시간 3: 세 번째 트럭(무게 5)이 다리에 올라갈 수 없다. (4 + 5 > 10)

• time = 3 (시간이 1 증가)
• qu = [[4, 4]]
• weightOnBridge = 4
• truck_weights = [5, 6]

시간 4: 두 번째 트럭(무게 4)이 다리를 건너고 세 번째 트럭(무게 5)이 다리에 올라간다.

• time = 4
• qu = [[5, 5]] (5kg 트럭이 시간 5에 다리를 건널 예정)
• weightOnBridge = 5
• truck_weights = [6]

시간 5: 세 번째 트럭(무게 5)이 다리를 건너고 마지막 트럭(무게 6)이 다리에 올라간다.

• time = 5
• qu = [[6, 7]] (6kg 트럭이 시간 7에 다리를 건널 예정)
• weightOnBridge = 6
• truck_weights = []

시간 6: 마지막 트럭이 다리 위에 있다.

• time = 6 (시간이 1 증가)
• qu = [[6, 7]]
• weightOnBridge = 6
• truck_weights = []

시간 7: 마지막 트럭(무게 6)이 다리를 건넌다.

• time = 7
• qu = []
• weightOnBridge = 0
• truck_weights = []

시간 8: 모든 트럭이 다리를 건넜고 함수가 종료.

• 결과값: time = 8

2. 이 문제에서 핵심은 다리 위에 있는 트럭이 무게를 초과했을때 어떻게 처리할 것인지가 문제였다. 결국 가장 앞에 있는 트럭 먼저 빨리 내보내기 위해서 시간을 앞에 있는 트럭에 맞춰서 내보내게 처리를 했다. 그리고 왜 time + bridge_length를 했는지에 대해서 궁금할 수도 있는데, 이유는 트럭이 다리를 완전히 건너기 위해 필요한 시간을 계산하기 위해서다. 다리의 길이(bridge_length)가 트럭이 다리를 건너는데 걸리는 시간을 의미한다. 트럭이 다리에 올라가는 시점이 time이니까 트럭이 다리를 완전히 건너기 위해서는 두 개의 값을 합쳐야 한다. 

 

 

▶ 배운점

1. 스택 & 큐 문제인데 다리의 무게 제한을 초과하지 않도록 처리하는 시뮬레이션 문제이기도 하다. 이런 유형에 익숙하지 않다보니 많이 풀어봐야겠다.

 

2. 이런 문제는 어떤 예외가 발생했을 시에 어떻게 처리하는지가 중요하다. 시험에서 나온다면 빠른 두뇌회전이 요구될 거 같다.