문제

https://programmers.co.kr/learn/courses/30/lessons/42583?language=java

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public int solution(int bridge_length, int weight, int[] truck_weights) {
    LinkedList<Truck> queue = new LinkedList<Truck>();

    for (int i = 0; i < truck_weights.length; i++) {
        queue.offer(new Truck(bridge_length, truck_weights[i]));
    }

    int answer = 1;
    int bridgeOnTruck = 0;
    while (!queue.isEmpty()) {

        int totalWeight = 0;
        for (int i = 0; i < bridgeOnTruck; i++) {
            totalWeight += queue.get(i).weight;
        }

        int nextWeight = 0;
        if (queue.size() > bridgeOnTruck) {
            nextWeight = queue.get(bridgeOnTruck).weight;
        }

        if (totalWeight + nextWeight <= weight) {
            if (queue.size() > bridgeOnTruck) {
                ++bridgeOnTruck;
            }
        }

        for (int i = 0; i < bridgeOnTruck; i++) {
            Truck truck = queue.get(i);
            truck.position = truck.position - 1;
        }

        if (queue.peek().position == 0) {
            queue.poll();
            --bridgeOnTruck;
        }

        ++answer;
    }

    return answer;
}

class Truck {
    public int position;
    public int weight;

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

흐름

  1. 트럭 array를 queue에 모두 저장
  2. 트럭 모두 건널 때 까지 반복
  3. 한 번에 몇 개의 트럭까지 건널 수 있을 지 계산하기 위해 현재 다리 위에 있는 트럭의 개수 만큼 돌면서 트럭 무게를 더함
  4. 다음 번 트럭까지 다리에 올라 올 수 있는 지 확인하기 위해 큐의 마지막 index가 아니라면 queue에서 다음 번 트럭의 무게를 가져옴
  5. 현재 다리에 있는 트럭들의 무게 + 다음 트럭의 무게를 더한 값이 다리가 버틸 수 있는 무게 보다 가벼우면
  6. 큐의 마지막인지 체크해서 큐의 마지막이 아니라면 그 다음 트럭도 다리 위에 올라와야 하기 때문에 다리 위 트럭의 개수(truckAmount)를 증가 시킴
  7. 다리 위 트럭의 수 만큼 반복하면서 트럭을 앞으로 한칸 씩 움직임
  8. 첫 번째 트럭이 다리를 건넜다면 queue에서 제거하고 다리 위 트럭 수를 하나 감소 시킴
  9. 초를 증가 시킴
  10. 끝

결과

번호 속도
테스트 1 통과 (3.63ms, 52.1MB)
테스트 2 통과 (14.16ms, 52.1MB)
테스트 3 통과 (1.65ms, 53.3MB)
테스트 4 통과 (41.49ms, 53.8MB)
테스트 5 통과 (70.64ms, 53.9MB)
테스트 6 통과 (53.31ms, 56.1MB)
테스트 7 통과 (3.09ms, 50MB)
테스트 8 통과 (1.97ms, 50.3MB)
테스트 9 통과 (10.68ms, 54.6MB)
테스트 10 통과 (2.20ms, 53MB)
테스트 11 통과 (1.10ms, 52.5MB)
테스트 12 통과 (2.35ms, 52.2MB)
테스트 13 통과 (4.50ms, 52.2MB)
테스트 14 통과 (1.26ms, 53MB)

테스트 케이스

1
2
3
assertEquals(8, test.solution(2, 10, new int[] {7,4,5,6}));
assertEquals(101, test.solution(100, 100, new int[] {10}));
assertEquals(110, test.solution(100, 100, new int[] {10,10,10,10,10,10,10,10,10,10}));