[프로그래머스] 스택/큐 - 다리를 지나는 트럭 문제 풀이(효율성 풀이)

지난번에 프로그래머스에서 스택/큐 문제 중 다리를 지나는 트럭의 문제 풀이를 했었습니다. 하지만 그 때 채점 결과에서 효율성이 좋지 않다는 내용을 확인하여 이번에는 알고리즘 개선을 하여 더 효율적인 문제 풀이 방법을 공부해보고자 합니다. 그럼 어떻게 알고리즘 개선을 할 수 있는지 알아보겠습니다.

 

 

 

먼저 오늘 풀어볼 문제는 바로 어제 풀어봤던 다리를 지나는 트럭 문제입니다. 그럼 어제 Queue를 활용했지만 효율성에서의 부족함을 보여줬던 문제 풀이 포스팅은 아래 있으니 안보시고 오신 분께서는 먼저 공부하고 오시는 것을 추천드립니다.

 

 

 

 

2022.06.25 - [컴공생의 Knowledge/Algorithm] - [프로그래머스] 스택/큐 - 다리를 지나는 트럭 문제 풀이

 

 

 

 

그리고 지난 프로그래머스 다리를 지나는 트럭 문제 풀이에서의 효율성 부분의 완벽하지 않았던 내용을 확인하기 위해 지난 풀이에서 활용된 알고리즘을 보고 더 개선할 수 있는 부분에 대해서 짚어보겠습니다.

 

 

 

 

▨ 효율성 개선 전 알고리즘

1. 다리의 길이만큼 크기를 가진 Queue를 만든다.
▶ 굳이 다리길이 만큼의 길이를 가진 Queue를 활용해야할까?
     Queue 사이즈는 현재 올려진 트럭 개수 만큼이며,
     트럭의 다리를 건너기 위한 소요 시간은 함께 입력된 변수로 대체한다.
2. 트럭을 순서대로 선택한다.
   2-1. 다리가 견딜 수 있는 무게인지 확인하고, 다리에 올라갈 수 있는 개수를 확인하여 가능 여부를 판단한다.
      2-1-1. 가능하면, 트럭을 올린다.
      2-1-2. 불가능하면, 트럭을 올리지 않는다.
   2-2. 다리에 올려져 있는 트럭은 1칸 전진한다.
      2-2-1. 전진한 트럭이 다리를 빠져 나갔다면 다리 Queue에서 제거한다.
   2-3. 시간도 1초 흐른 후, 2로 이동한다.
  ▶ 1초씩 꼭 시간을 보내야할까?
       시간을 한번에 보낼 수 있는 로직도 함께 고려해야한다.
3. 모든 트럭이 빠져나왔으면 현재 흐른 시간을 반환한다.

 

 

 

그럼 알고리즘 부분에서 개선할 수 있는 부분을 보완해서 새로 알고리즘을 작성해보겠습니다.

 

 

 

▨ 효율성 개선 후 알고리즘

1. 배열을 만든다. 이 배열의 요소는 [트럭 무게, 트럭이 다리를 빠져나갈 시간]으로 구성한다.
2. 트럭을 순서대로 선택한다.
   2-1. 현재 지난 시간이 맨 앞에 있는 트럭이 다리를 빠져나갈 시간인지 확인한다.
      2-1-1. 트럭이 빠져나갈 시간이면, 다리에서 트럭을 제거한다.
   2-2. 다리가 견딜 수 있는 무게인지 확인하고, 다리에 올라갈 수 있는 개수를 확인하여 가능 여부를 판단한다.
      2-2-1. 가능하다면, 트럭을 올린다.
      2-2-2. 불가능하다면, 맨 앞 트럭이 빠져나갈 시간 바로 직전으로 시간을 보낸다. 
   2-3. 시간이 1초 지난다.
3. 모든 트럭이 빠져나왔으면 현재 흐른 시간을 반환한다.

 

 

위 알고리즘은 다리(배열)의 크기도 줄었으며, 1칸씩 증가하는 로직에서 한번에 맨 앞 트럭이 빠져나갈 때까지 계산하는 로직을 통해 동작도 줄어든 부분 확인할 수 있습니다. 그럼 마지막으로 코드 구현을 통해 알고리즘을 최종 점검해보겠습니다.

 

 

 

 

▨ 효율성 개선 후 코드 구현

function solution(bridge_length, weight, truck_weights) {
    var time = 0;
    // 1. 배열을 만든다. 이 배열의 요소는 [트럭 무게, 트럭이 다리를 빠져나갈 시간]으로 구성한다.
    const bridge = [];
    let weightsOnBridge = 0;
    let selected_truck = 0;
    
    do {
    	// 2. 트럭을 순서대로 선택한다.
        if (selected_truck === 0) {
            selected_truck = truck_weights.shift();
        }

        // 2-1. 현재 지난 시간이 맨 앞에 있는 트럭이 다리를 빠져나갈 시간인지 확인한다.
        if (bridge.length > 0 && bridge[0][1] === time) {
            // 2-1-1. 트럭이 빠져나갈 시간이면, 다리에서 트럭을 제거한다.
            weightsOnBridge -= bridge.shift()[0];
        }
        
        // 2-2. 다리가 견딜 수 있는 무게인지 확인하고, 다리에 올라갈 수 있는 개수를 확인하여 가능 여부를 판단한다.
        if(selected_truck && weightsOnBridge + selected_truck <= weight) {
            // 2-2-1. 가능하다면, 트럭을 올린다.
            weightsOnBridge += selected_truck;
            bridge.push([selected_truck, time + bridge_length]);
            selected_truck = 0;
        } else {
            // 2-2-2. 불가능하다면, 트럭이 빠져나갈 시간 바로 직전으로 시간을 보낸다. 
            if(bridge[0]) {
                time = bridge[0][1] - 1;
            }
        }
        // 2-3. 시간이 1초 지난다.
        time++;
    } while (truck_weights.length > 0 || weightsOnBridge > 0);
    // 3. 모든 트럭이 빠져나왔으면 현재 흐른 시간을 반환한다.
    return time;
}

 

 

위처럼 불필요한 동작을 최소화하기 위해서는 데이터 구조를 잘 설계해야하며, 최대한 조건에 빠르게 걸리게 알고리즘을 구상하여야 합니다. Queue를 활용하면서도 Queue의 데이터 구조를 [트럭 무게, 트럭이 다리를 빠져나갈 시간]이라는 배열의 형태로 알고리즘을 만드는데 있어 꼭 필요한 데이터를 추가함으로써 훨씬 효율성 있는 코드가 만들어질 수 있었습니다.

 

 

 

▨ 효율성 개선 후 채점 결과

 

 

 

정말 깔끔하게 1ms를 넘는 시간이 걸리는 테스트 케이스가 없이 완벽한 코드를 만들어 봤습니다. 이번에는 알고리즘과 데이터 구조를 효율성 있게 구현하는 방법을 공부해보았습니다.

 

 

앞으로 알고리즘 문제 풀이하는데 있어 꼭 필요한 지식과 경험이라 생각이 들며, 오늘도 함께 공부하시느라 고생하셨습니다.