[프로그래머스/JAVA] Level 2, 다리를 지나는 트럭

안녕하세요😎 백엔드 개발자 제임스입니다 :)

오늘은 [프로그래머스의 다리를 지나는 트럭] 문제를 포스팅하겠습니다. 분류는 스택가 큐에 해당하는데요. 코딩 테스트에 빈번하게 출현하는 문제 중 하나입니다. 비슷하게 프린터, 박스 포장 등에 문제도 있습니다. 따라서 자주 마주치는 문제이죠. 하지만 마주칠 때마다 어렵게만 느껴집니다. 

 

(Level 2) 다리를 지나는 트럭

---

1) Problem

요약 : 여러 대의 트럭들이 무게와 트럭 허용 길이가 정해진 다리를 모두 지나는 데 걸리는 시간을 구하시오.

예시

다리가 허용하는 길이는 2, 무게는 10입니다. 이때 무게가 각각 7, 4, 5, 6인 4대의 트럭이 있습니다. 모든 트럭이 다리를 지나가려면 8초가 걸립니다.

(1) 다리에 아무 트럭도 없기 때문에 첫 번째 트럭(7)이 다리에 올라갑니다. 이때 1초가 지나갑니다.

(2) 다리의 제한 무게(10)로 인해서 무게가 4인 트럭은 이어서 올라갈 수 없습니다. 이제 2초가 됩니다.

(3) 즉, 무게가 7인 트럭이 다리를 모두 지나가야만 합니다. 

(4) 다음은 무게 5인 트럭이 올라와도 다리의 제한 무게 이내이기 때문에 두 개의 트럭이 올라올 수 있습니다. 이때 4초가 됩니다.

위와 같이 트럭이 한 칸 지나갈 때마다 1초가 지나갑니다. 이러한 방식으로 진행했을 때, 모든 트럭이 지나가면 8초가 지납니다.

 

2) 풀이

코드는 아래 더보기를 클릭해주세요.

---

public int solution(int bridge_length, int weight, int[] truck_weights) {
    int time = 0;
    Queue<Integer> bridge = new LinkedList<>();
    int index = 0;

    while (index < truck_weights.length) {
        int currTruck = truck_weights[index];

        if (bridge.isEmpty()) {
            bridge.add(currTruck);
            index++;
            time++;
        } else if (bridge.size() < bridge_length) {

            if (isPermitWeight(getCurrWeightInBridge(bridge), currTruck, weight)) {
                bridge.add(currTruck);
                index++;
            } else {
                bridge.add(0);
            }

            time++;

        } else {
            bridge.poll();
        }
    }
    return time + bridge_length;
}

public int getCurrWeightInBridge(Queue<Integer> bridge) {
    return bridge.stream().mapToInt(a -> a).sum();
}

public boolean isPermitWeight(int currWeightInBridge, int currTruckWeight, int limit) {
    return currWeightInBridge + currTruckWeight <= limit;
}

---

(1) Queue 자료구조 활용

보다시피 다리를 지나가는 트럭들은 들어온 순서대로 나갑니다. 따라서 Queue 자료를 활용할 수 있습니다.

(2) 상황별 구현

위에 예시를 봤을 때, 네 가지의 상황을 뽑을 수 있습니다.

1. 다리에 어떤 트럭도 없을 경우
2. (다리 위에 트럭이 있을 때) 현재 다리에 있는 트럭의 무게와 다음 트럭의 무게를 합쳤을 때, 제한 무게를 초과하지 않는 경우
3. (다리 위에 트럭이 있을 때) 현재 다리에 있는 트럭의 무게와 다음 트럭의 무게를 합쳤을 때, 제한 무게를 초과하는 경우
4. 이미 다리의 허용 길이만큼 트럭이 있을 경우

(3) 풀이

해당 문제는 while문을 통해서 트럭을 이동시키려고 했습니다. 트럭이 모두 지나갔을 때의 결과를 구하는 것이기 때문에 트럭이 들어있는 배열의 모든 요소가 모두 사용되면 반복문을 종료하게 했습니다. 저는 index라는 변수를 따로 선언했습니다. 해당 변수를 통해서 배열에서 현재 지나갈 트럭을 지정하게 했습니다.

다시 언급하자면, 배열의 마지막 트럭이 다리에 올라가면 while문이 종료됩니다.

각 상황에 맞게 구현합니다. 다리에 어떤 트럭도 없거나, 제한무게 이내라면 현재 지정된 트럭이 다리에 올라옵니다. 그리고 index는 다음 올라올 트럭을 지정합니다.

만약 제한무게를 초과할 경우에는 0을 추가합니다. 해당 0을 통해서 다리의 공백을 나타냅니다. 이 모든 과정마다 시간이 추가됩니다. 그리고 결국 트럭은 다리를 지나가야 하기 때문에 길이가 2가 되면, 가장 앞에 있는 트럭을 제거하면 됩니다. 이때 Queue의 poll 메서드를 통해서 제거합니다.

하지만 시간은 추가되지 않습니다.

* 중요 Point
여기서 중요한 것은 트럭이 추가될 때만 시간을 추가합니다. 위 예시를 봤을 때, 다리 위에 트럭이 제거되면서, 새로운 트럭이 추가되는데 이때 1초 안에 발생하기 때문입니다. 다시 말하자면, 다음 트럭이 들어오면서 제일 앞 트럭을 밀어낸다고 생각하면 좋습니다.

위에서 언급한 대로 마지막 트럭이 다리에 올라서면 while 반복문은 종료됩니다. 그리고 결과는 지금까지 연산된 시간에서 다리 길이만큼 더해진 만큼에 값이 됩니다.

지금까지 보자면, 트럭이 한 칸 이동할 때마다 1초가 지나갑니다. 즉, 트럭이 다리의 첫 부분부터 끝까지 가는 데 걸리는 시간은 [다리 길이 - 1] 초가 걸리게 됩니다. 여기에 한 칸을 더 이동하여 다리를 벗어나기 때문에 결국 다리를 지나가는 데 걸리는 시간은 [다리 길이]라고 할 수 있습니다.

현재 마지막 트럭이 다리에 올라간 채 반복문이 종료되었기 때문에, 지금까지 구한 시간에서 다리 길이만큼 더한 값이 결과가 되는 것입니다.

 

3) 시행착오

저는 여러 가지 시행착오로 문제를 푸는데 시간이 꽤 걸렸습니다.

가장 먼저 다리 길이가 고정이 아니라는 점에서 어려움을 겪었습니다. 여기에 트럭들의 무게도 중복일 수가 있었습니다. 따라서 단순히 index로만 풀기에는 한계가 있었습니다. 가령 index로 트럭 위치에 따라 구현 방법을 달리했으나 중복되는 값들의 이유로 문제를 명확하게 풀지 못했습니다.

다음은 적절하게 시간을 추가하지 못했습니다. 따라서 어떠한 테스트는 성공하나 또 다른 경우에는 틀리게 되었습니다.

이를 해결하기 위해 많은 고민을 했는데요. 중간엔 상황에 따라 시간이 추가되는 값이 다르다는 것을 파악하고 이를 하나하나 다 적용했습니다. 하지만 변수가 너무 많아 실패했습니다.

스터디 팀원의 문제 풀이 방식이 문득 떠올랐습니다. 문제를 풀기 위해 세 가지의 배열을 선언했었습니다. 첫 번째는 다리 역할의 배열, 두 번째는 도착한 트럭의 정보를 저장할 배열, 세 번째는 무게 중복으로 인한 문제를 방지하기 위한 index 체크용 배열이었습니다.
트럭이 다리를 지날 때마다 각 정보를 배열에 저장한 방식이었는데요. 해당 방법을 일찍 생각했다면, 중복에 대한 시행착오를 빠르게 해결했을 수 있었겠네요.