[PGM_42583] 다리를 지나가는 트럭

문제링크

https://programmers.co.kr/learn/courses/30/lessons/42583

코딩테스트 연습 - 다리를 지나는 트럭

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 큐

1. 문제 이해

모든 트럭이 다리를 지나가는데 걸리는 시간을 구하는 문제이다. 이 때 트럭이 지나가는 다리의 길이와 가능한 무게가 주어진다. 트럭 한대가 지나가는데 걸리는 시간은 다리의 길이이다. 그리고 트럭이 올라갈 수 있는 한계는 다리의 길이만큼과 다리가 버틸 수 있는 무게의 이하일 경우이다.

 

2. 접근방법

문제를 해결하기 위하여 큐를 사용하여 해결하였다.

Queue를 활용하여 도로위에 올라온 트럭을 표시하여주고, 트럭이 일정 시간이 지나고 도로에서 빠져나가는 상황을 구현하였다.

 

모든 트럭에 대하여 아래의 과정을 진행한다.

1) 트럭이 올라갈 수 있는지 확인한다.(트럭 무게 <= 남은 다리가 버틸 수 있는 무게)

 - 올라 갈 수 있다면 queue에 값을 넣어준다.

 - 올라갈 수 없다면 queue의 값을 빼주고 그 시간만큼 이동한다.

2) 가장 처음에 올라간 트럭을 확인하여 다리를 모두 지났는지 확인해준다.

 - 다리를 지났다면 큐에서 제거하여준다.

 

위 과정을 모든 트럭에 대하여 체크하여 주면 문제를 해결 할 수 있다.

구현코드

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int count = 0;
        int roadWeight = 0;
        Queue<int[]> road = new LinkedList<>();
        int ptr = 0;

        //트럭 다리 위로 올리기
        while (ptr < truck_weights.length){
            count++;

            //트럭이 통과할 때
            if(!road.isEmpty() &&count-road.peek()[1] == bridge_length){
                int[] truck = road.remove();
                roadWeight -= truck[0];
            }

            //트럭이 올라갈 때
            if(truck_weights[ptr] + roadWeight <= weight){
                road.add(new int[]{truck_weights[ptr],count});
                roadWeight += truck_weights[ptr];
                ptr ++;
            }
            //무게 초과로 더 이상 올릴 수 없는 경우
            else{
                int[] truck = road.remove();
                roadWeight -= truck[0];
                count += truck[1] + bridge_length-count-1;
            }
        }

        //다리에 남아있는 트럭 옮기기
        while (!road.isEmpty()){
            int[] truck = road.remove();
            count += truck[1] + bridge_length-count;
        }
        return count;
    }
}

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)