[42583] 다리를 지나는 트럭

✔ 다리를 지나는 트럭

[프로그래머스 42583]

문제 분석하기

큐에 하나의 트럭을 집어 넣은 후

다음 트럭을 집어넣었을 때 최대 무게보다 적다면 큐에 집어 넣고, 그렇지 않다면 0을 넣어 앞의 트럭이 전진하여 건너도록 함

이때 시간 초를 증가시켜 줌

경과 시간	대기 트럭	다리를 건너는 트럭	다리를 지난 트럭
0	[7, 4, 5, 6]	[_, _]	[]
1	[4, 5, 6]	[7, _]	[]
2	[4, 5, 6]	[_, 7]	[]
3	[5, 6]	[4, _]	[7]
4	[6]	[5, 4]	[7]
5	[6]	[_, 5]	[7, 4]
6	[]	[6, _]	[7, 4, 5]
7	[]	[_, 6]	[7, 4, 5]
8	[]	[]	[7, 4, 5, 6]

손으로 풀어보기

1. 큐에 하나의 트럭을 집어 넣음
2. 앞에 존재하는 트럭과 현재 집어 넣을 트럭의 무게의 합을 최대 무게와 비교
   • 함께 다리를 건널 수 있는 트럭이 존재하지 않는다면 0을 집어 넣도록 함
   • 함께 다리를 건널 수 있는 트럭이 존재한다면 트럭을 집어 넣도록 함
   • 큐에 삽입과 삭제가 발생할 때 시간 초 증가
3. 최소 시간 반환

슈도코드 작성하기

bridge_length(다리에 올라갈 수 있는 트럭 수)
weight(다리가 견딜 수 있는 무게)
truck_weights(트럭 별 무게)
answer(모든 트럭이 다리를 건너는 최소 시간)
sum(다리 위 트럭의 무게 합)
queue(트럭이 지나가는 다리)
for(weight만큼) {
    while(true) {
        if(queue가 비어있다면) {
            트럭 하나를 다리에 올린 후, 다음 트럭으로
        }
        else if(queue.size() == bridge_length) {
            다리의 가장 앞의 트럭을 다리에서 뺌
        }
        else {
            if(sum + 트럭 <= weight) {
                트럭 하나를 다리에 올린 후, 다음 트럭으로
            }
            else {
                올릴 수 있는 트럭이 없다면 0을 넣어, 앞의 트럭이 앞으로 이동하도록 함
            }
        }
    }
}
answer에 마지막 트럭이 건너는 시간인 bridge_length를 합하여 반환

코드 구현하기

/**
 * 42583) 다리를_지나는_트럭
 */
public class K005_42583 {
    // bridge_length(다리에 올라갈 수 있는 트럭 수)
    // weight(다리가 견딜 수 있는 무게)
    // truck_weights(트럭 별 무게)
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        // answer(모든 트럭이 다리를 건너는 최소 시간)
        int answer = 0;
        // sum(다리 위 트럭의 무게 합)
        int sum = 0;
        // queue(트럭이 지나가는 다리)
        Queue<Integer> queue = new LinkedList<>();
        for (int truck : truck_weights) {
            while (true) {
                // queue가 비어있다면
                if (queue.isEmpty()) {
                    // 트럭 하나를 다리에 올린 후, 다음 트럭으로
                    queue.add(truck);
                    sum += truck;
                    answer++;
                    break;
                }
                // queue가 꽉 찼다면
                else if (queue.size() == bridge_length) {
                    // 다리의 가장 앞의 트럭을 다리에서 뺌
                    sum -= queue.poll();
                } else {
                    // 다리에 트럭 하나를 더 올릴 수 있다면
                    if (sum + truck <= weight) {
                        // 트럭 하나를 다리에 올린 후, 다음 트럭으로
                        queue.add(truck);
                        sum += truck;
                        answer++;
                        break;
                    } else {
                        // 올릴 수 있는 트럭이 없다면 0을 넣어, 앞의 트럭이 앞으로 이동하도록 함
                        queue.add(0);
                        answer++;
                    }
                }
            }
        }
        // answer에 마지막 트럭이 건너는 시간인 bridge_length를 합하여 반환
        return answer + bridge_length;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        K005_42583 solution = new K005_42583();

        int bridge_length = 2;
        int weight = 10;
        int[] truck_weights = { 7, 4, 5, 6 };
        int result = solution.solution(bridge_length, weight, truck_weights);

        System.out.println(result);
    }
}