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

※ 해당 문제의 링크는 여기입니다. ※

Inner Class를 사용해 문제를 해결하였습니다.

 

제한사항

1. bridgeLength 길이의 다리가 있고, 정해진 순서에 맞춰 트럭이 건너가야 한다.
2. 트럭마다 무게가 각각 존재한다.
3. bridgeLength길이만큼 트럭을 다리 위로 이동시킬 수 있으나, 다리가 최대로 버틸 수 있는 무게는 정해져 있다.
4. 트럭은 한 번에 1씩만 움직일 수 있고, bridgeLength만큼 전부 움직여야 다리를 완전히 건넌 것이다.
5. 한 번에 하나의 행동만 가능하다. (동시에 트럭을 2대 이상 이동시킬 수 없음)

위 문제에 자세히 설명이 되어있지 않아, 문제를 풀어서 설명하였습니다.

 

알고리즘

문제를 이해하는 데에 오래 걸렸습니다. 질문하기에서도 많은 분들이 문제를 이해하기 어려워하셨습니다.

문제를 이해하고 나면 실제 풀이는 그리 오래 걸리지 않았습니다.

저는 Inner Class를 사용하였으니, 더 간단하게 해결하였습니다.

public static class Truck {
    private final int weight;
    private int moved;

    public Truck(int weight) {
        this.weight = weight;
        this.moved = 0;
    }

    public int getWeight() {
        return weight;
    }

    public void move() {
        moved++;
    }

    public int getMoved() {
        return moved;
    }
}

Truck이라는 Inner Class입니다.

생성자로 무게를 지정받고, 기본 위치는 0입니다.

 

Queue<Truck> trucks = new ArrayDeque<>();
for (int truck : truckWeights) {
    trucks.add(new Truck(truck));
}

트럭 Queue에 각 무게별로 트럭 인스턴스 화하여 추가합니다.

trucks는 아직 건너지 않은 트럭들입니다.

 

int i = 0;

총 행동 횟수, 즉 문제에서 말하는 시간입니다.

while문을 사용하여 계산할 것이기에

카운트 변수를 따로 지정하였습니다.

 

ArrayList<Truck> bridge = new ArrayList<>();    // 다리

현재 다리 위에 있는 트럭을 저장하기 위한 ArrayList입니다.

 

while(!trucks.isEmpty() || !bridge.isEmpty()) {
}

건너지 않은 트럭이 없고, 다리 위에 아무런 트럭이 없을 때 while문이 break 됩니다.

 

for (Iterator<Truck> truckIterator = bridge.iterator(); truckIterator.hasNext();) {
    Truck currentTruck = truckIterator.next();
    currentTruck.move();
    if (currentTruck.getMoved() >= bridgeLength) {
        truckIterator.remove();
    }
}

반복문 중 배열 혹은 리스트 등을 삭제하게 되면 ConcurrentModificationException이 발생하게 됩니다.

하지만 Iterator를 사용하게 되면 문제없이 해결된다.

(물론 list 역시 exception 없이 작동하게 되지만, 이상한 값이 사라지게 된다.

이는 중간에 값이 사라졌기에 위치에 이상이 발생하게 되기 때문이다.)

자바 공식 튜토리얼에서도 위 방식이 가장 safe 한 방법이라고 알려주고 있습니다.

 

int weights = 0;
for (Truck bridgeTruck : bridge) {
    weights += bridgeTruck.getWeight();
}

무게를 계산을 합니다. (더 편한 방법 등이 있겠지만, 그냥 복잡하게 계산하기 싫었습니다.)

 

if (!trucks.isEmpty()) {
    if (weights + trucks.peek().getWeight() <= weight) {
        bridge.add(trucks.poll());
    }
}
i++;

아직 건너지 않은 트럭들이 있다면

무게를 계산하여 다리에 추가해줍니다.

(다리에 아무런 트럭들이 없으면 0이므로 이 역시 자동으로 트럭이 추가됩니다.)

그 후, 행동을 했으므로 카운트해줍니다.

 

전체 소스코드

import java.util.*;

class Solution {

    public static class Truck {
        private final int weight;
        private int moved;

        public Truck(int weight) {
            this.weight = weight;
            this.moved = 0;
        }

        public int getWeight() {
            return weight;
        }

        public void move() {
            moved++;
        }

        public int getMoved() {
            return moved;
        }
    }

    public int solution(int bridgeLength, int weight, int[] truckWeights) {
        Queue<Truck> trucks = new ArrayDeque<>();
        for (int truck : truckWeights) {
            trucks.add(new Truck(truck));
        }

        int i = 0;
        ArrayList<Truck> bridge = new ArrayList<>();    // 다리
        while(!trucks.isEmpty() || !bridge.isEmpty()) {
            for (Iterator<Truck> truckIterator = bridge.iterator(); truckIterator.hasNext();) {
                Truck currentTruck = truckIterator.next();
                currentTruck.move();
                if (currentTruck.getMoved() >= bridgeLength) {
                    truckIterator.remove();
                }
            }

            int weights = 0;
            for (Truck bridgeTruck : bridge) {
                weights += bridgeTruck.getWeight();
            }

            if (!trucks.isEmpty()) {
                if (weights + trucks.peek().getWeight() <= weight) {
                    bridge.add(trucks.poll());
                }
            }
            i++;
        }

        return i;
    }
}

 

추가로...

시간 복잡도가 좋지 않습니다.

테스트 케이스 5번에서는 무려 51.7ms나 소모되었습니다.

그래도 대부분의 코딩 테스트들의 제한시간이 1초 ~ 0.5초 정도인 것을 감안한다면

심각한 문제는 아니라고 생각이 듭니다.

(1 sec = 1000ms)

 

 

이상입니다.