[알고리즘 문제 풀이] 프로그래머스 - 다리를 건너는 트럭

문제 원본 링크: https://programmers.co.kr/learn/courses/30/lessons/42583

카테고리: 스택/큐

 

문제 설명

트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순서로 건너려 한다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 한다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리의 무게는 weight까지 견딘다. 

* 트럭이 다리에 완전히 오르지 않으느 경우, 이 트럭의 무게는 고려하지 않는다.

 

예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있다. 무게가 [7, 4, 5, 6]kg인 트럭들이 순서대로 최단 시간에 다리를 건너려면 다음과 같이 건너야 한다. 

따라서 모든 트럭이 다리를 지나려면 최소 8초가 걸린다. 

 

solution 함수의 매개변수로 다리길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭별 무게 truck_weights가 주어진다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하라. 

 

제한 조건 

• bridge_length는 1 이상, 10,000 이하이다.

• weight는 1 이상 10,000 이하이다. 

• truck_weights의 길이는 1 이상 10,000 이하이다. 

• 모든 트럭의 무게는 1 이상 weight 이하이다. 

입출력 예

내 풀이 과정

1. while 문이 한 번 진행될 때 1초가 흐른다고 가정한다.

2. 그리고 다리 위의 트럭은 1만큼 앞으로 전진한다.

3. 1초마다 아래의 항목들을 수행한다.

   1. answer + 1

   2. 다리위 트럭이 하나도 없으면 종료한다.

   3. 다리위 트럭들의 무게의 합을 구한다.

   4. 다리위 트럭의 위치 +1

   5. 다리의 무게에 여유가 있으면 새로운 트럭이 건너기 시작한다.

 

자바 코드

public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;

        Queue<Integer> waitingTrucks = new LinkedList<>();
        Queue<Truck> passingTrucks = new LinkedList<>();

        for (int w : truck_weights) waitingTrucks.offer(w);

        while (true) {
            if (passingTrucks.isEmpty()) {
                // 모든 트럭이 건넜으면 반복문 종료
                if (waitingTrucks.isEmpty()) break;
                else passingTrucks.offer(new Truck(waitingTrucks.poll(), 0));

            } else {
                int totalWeight = 0;
                // 다리 위의 트럭을 1만큼 전진
                for (Truck truck : passingTrucks) {
                    truck.position++;
                    totalWeight += truck.weight;
                }

                // 모두 건넌 트럭은 제외
                if (passingTrucks.peek().position == bridge_length) {
                    totalWeight -= passingTrucks.peek().weight;
                    passingTrucks.poll();
                }

                // 대기중인 트럭이 아직 있고 다리 위 무게 여유가 있다면 건너기 시작
                if (!waitingTrucks.isEmpty() && waitingTrucks.peek() + totalWeight <= weight)
                    passingTrucks.offer(new Truck(waitingTrucks.poll(), 0));
            }

            answer++;
        }

        return answer;
    }

    private static class Truck {
        int weight;
        int position;

        public Truck(int weight, int position) {
            this.weight = weight;
            this.position = position;
        }
    }

Truck 클래스를 만들어 무게와  위치를 저장할 수 있도록 구현했다.

이번에도 코드가 간결하지는 않아서 아쉽다. 쩝.

 

채점 결과

 

참고

- 깃허브 소스: 링크